# Maximum sum of all the possible sub-arrays

Page Contents

### Maximum sum of all the possible sub-arrays

Q1: Given an array with integers, what is the maximum sum of all the possible sub-arrays?

Analysis:
There are (N*(N+1))/2 distinct sub-arrays in total. Thus, if we check each one step by step, the time complexity is O(N^2), which gives an upper-bound of our methods.

Can we do better?

The general idea is:
1): get the maximum sum for all the subarrays ending with each element;
2): get the maximum of all the maximum sums obtained in 1).

Imagine we have handled the situation for all the elements to (i-1). Now we need to deal with the ith element.

Let define sum as the maximum sum ending the (i-1), and res is the maximum sum in the range from 0 to (i-1).

Then,  we need to update sum to make it ending with the ith element,

sum = max(sum + arr[i], arr[i])

then, we can update the res by choosing the maximum,

res = max(res, sum)

So now the sum is the maximum sum of subarrays ending with the ith element;
res is the maximum sum of subarrays in the range of [0, i].

See the code below:

class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
if(!n) {
cout<<“invalid input!”;
return 0;
}
int res = nums[0], sum = nums[0];
for(int i=1; i<n; ++i) {
sum = max(sum + nums[i], nums[i]);
res = max(res, sum);
}
return res;
}
};

The above time complexity is O(N), the space complexity is O(1).

Let try a different way: let use sum[i] represents the continuous sum from arr[0] to arr[i]. Then the maximum subarray sum (ending with the ith element) should be:
max(sum[i] – sum[j])   where j>=0 and j< i;
which is equivalent to:
sum[i]  –  min(sum[j])   where j>=0 and j<i;

Since we have known all the sum[j] before sum[i], thus we can just use one variable minSum to memorize this.

Then the key formula becomes;
minSum = min(minSum, sum[i-1]); // minimum {sum[j]} where j in [0, i-1]
sum [i] = sum[i-1] + arr[i]; // update sum to the current ith element;
maxDiff = sum[i] – minSum; // maximum sum ending with the ith element;
res = max(res, maxDiff); // maximum sum in [0, i]

Since we only need sum[i-1] and sum[i], we can use only one variable sum for this:
minSum = min(minSum, sum); // minimum {sum[j]} where j in [0, i-1]
sum  = sum + arr[i]; // update sum to the current ith element;
maxDiff = sum – minSum; // maximum sum ending with the ith element;
res = max(res, maxDiff); // maximum sum in [0, i]

class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
if(!n) {
cout<<“invalid input!”;
return 0;
}
int res = nums[0], sum = nums[0], minSum = min(0, nums[0]);
for(int i=1; i<n; ++i) {
minSum = min(minSum, sum);
sum += nums[i];
res = max(res, sum – minSum);
}
return res;
}
};

The time complexity is still O(N), and space complexity is O(1).