Subarray Problems

Maximal Subarray

Given an unsorted array s[0:n], find a subarray s[i:j] that maximize sum(s[i:j]).

sum(s[i:j]) equals to sum(s[0:j]) - sum(s[0:i-1]), in which sum(s[0:j]) is a fixed value when j is known. Hence maximizing sum(s[i:j]) becomes minimize sum(s[0:i-1]), where i-1 < j.

Therefore we need sum(s[0:i]), and the minimum subarray min(s[0:k]) where k < i to calculate max(s[i:j]).

sum(s[0:i]) = s[0:i]
min(s[0:k]) = min(sum(s[0:k-1]), sum(s[0:k]))
max(s[k+1:j]) = max(sum(s[0:j]), sum(s[0:j]) - min(s[0:k]), max(s[k+1:j-1]))

Minimal Subarray

Similar idea but we need to keep the minimal s[0:k].