Maximum sum of all the possible sub-arrays

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 answer is yes. 
 
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).

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

1. Frog Sort Solution Codechef

2. Chef and Meetings Solution Codechef

3. Maximise Function Solution Codechef

4. Highest Divisor Solution Codechef

5. Cut the Cake Challenge Solution Codechef

6. Dream and the Multiverse Solution Codechef

7. Cell Shell Solution Codechef

8. Multiple Games Solution Codechef

9. Another Tree with Number Theory Solution Codechef

10. XOR Sums Solution Codechef

11. Prime Game Solution CodeChef

12. Team Name Solution Codechef

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :

Leave a Comment