Maximum Subarray Sum

What we are trying to solve?

Let’s say we have an array, we have to find out the subarray such that the sum of the elements in that subarray is maximum & we have to return its sum.

So, what are the possible ways we can solve this?

1. Brute Force - We can generate all the subarrays using two for loops & can compare the accumulated values of that subarray with the maximum value. After the iteration gets over we can return the maximum value.

   • What will be expected time complexity?

     • O(n^2) for generating all the subarrays

     • O(n) to accumulate the sum of that subarray – this can be done on the go then we can reduce the time complexity

         int maxSum(vector<int>& arr) {
             int n = arr.size();
             int maxi = INT_MIN;
             for (int i = 0; i < arr.size(); i++){
                 for (int j = i; j < arr.size(); j++){
                     int sum = 0;
                     for (int k = i; k <= j; k++){ 
                         sum += arr[k];
                     }
                     maxi = max(maxi, sum);
                 }
             }
             return maxi;
         }
       

       Time Complexity - O(n^3)
       Space Complexity - O(1)

2. Optimization - Where we are using the for loop to accumulate the sum of the subarray, there we can do a simple modification to avoid the recomputation of sum again and again. Thus,

    int maxSum(vector<int>& arr) {
        int n = arr.size();
        int maxi = INT_MIN;
        for (int i = 0; i < arr.size(); i++){
            int sum = 0;
            for (int j = i; j < arr.size(); j++){
                sum = arr[j];
                maxi = max(maxi, sum);
            }
        }
        return maxi;
    }
   

   Time Complexity - O(n^2)

   Space Complexity - O(1)

After solving this in an interview the interviewer may not be happy with the quadratic time complexity & he may ask to do this in linear time complexity, then we have to learn -

3. Kadane’s Algorithm

   Before we jump directly into the solution I would love to give you a demonstration below, are you observing something ?

   

   Observations

   1. When the sum is positive then we are comparing the value with previous maximum value (i.e. maxi) and carrying the sum because it has a contribution to the upcoming sum.

   2. When the sum becomes negative there is no need to carry the previous accumulated sum because we have to maximize the sum. If the previous sum is giving me a negative total then it will reduce my result at the end of the day.

       int maxSubArray(vector<int>& nums) {
               int sum = 0;
               int maxi = INT_MIN;
               for(int i = 0; i<nums.size(); i++){
                   sum += nums[i];
                   if (sum > maxi) maxi = sum;
                   if (sum < 0) sum = 0;
               }
               return maxi;
       }
      

      Time Complexity - O(n)

      Space Complexity - O(1)

Note: If you find any bugs, please share your thoughts in the comments below.