Oct-02-2019, 09:04 PM
It seems easy if you define
s[j] = sum(arr[i] for i in range(j))
because if the maximum sum of contiguous subarrays is reached for a the range(a, b) of indices, with a <= b, then this sum is s[b] - s[a]
and for all c <= b one has s[b] - s[c] <= s[b] - s[a]
which means that s[a] <= s[c]
, hence s[a] is the minimum value of s
for all indices smaller than b. Hence the algorithmstart with mv = 0 and sv = 0 and best = 0 for b in range(n): sv += arr[b] mv = min(mv, sv) best = max(best, sv - mv) return best