Solution by hmsingh


  • 0
    H

    Approach #1 Brute Force [Accepted]

    Intuition

    Get the maximum sum subarray starting at each index. The maximum of these sums would be the ultimate maximum sum.

    Algorithm

    Traverse the vector using nested loops. The outer loop index would be the starting point of the subarray and the inner nested loop would be different end points for that subarray.

    At each end point in the nested loop, we would adjust the max for the subarray starting at i and ending at j and at the end of loop, adjust the max if the array starting at index i have the maximum sum till now.

    C++

    public class Solution {
        int maxSubArray(vector<int>& nums) {
            int localmax = INT_MIN; //the maximum sum for the subarray starting at index i
            int max = INT_MIN; // the overall maximum sum
    
            for(int i=0; i<nums.size(); ++i) {
                // Get max sum for the subarray starting at index i
                int sum = 0;
                for(int j=i; j<nums.size(); ++j) {
                    sum+=nums[j];
                    if(localmax < sum)
                        localmax = sum;
                }
                if(localmax > max)
                    max = localmax;
            }
            return max;
        }
    };
    

    Complexity Analysis

    • Time complexity : $$O(n^2)$$.

      We have 2 loops, one traversing the vector treating each element as the starting point of the subarray and the inner loop treating each index of the vector as the endpoint of that subarray.

      For a given i, we traverse all the elements at index greater to i of the vector.
      Thus, the time complexity of this Algorithm is $$O(n^2)$$.

    • Space complexity : $$O(1)$$ as we are not using any extra variable space.

    Approach #2 Divide and Conquer Approach [Accepted]

    Algorithm

    The approach is to divide the problem into sub-problems and get the maximum sum subarray.

    We can divide the problem into max of following:

    1. The maximum sum of the left half of the vector,
    2. The maximum sum of the right half of the vector,
    3. The maximum sum of the subarray containing the middle element.

    C++

    class Solution {
    private:
        int maxSubArrayCrossed(vector<int>& nums, int l, int m, int h) {
            // max sum from m->0 + max sum from m+1->h
            int left_sum = INT_MIN;
            int sum = INT_MIN;
            for(int i=m; i>=l; --i) {
                sum += nums[i];
                if(left_sum < sum) {
                    left_sum = sum;
                }
            }
            
            int right_sum = INT_MIN;
            sum = INT_MIN;
            for(int i=m+1; i<=h; ++i) {
                sum += nums[i];
                if(right_sum < sum) {
                    right_sum = sum;
                }
            }
            return left_sum + right_sum;
        }
        
        int maxSubArrayHelper(vector<int>& nums, int l, int h) {
            if(l==h)
                return nums[l];
            int m = l+(h-1)/2;
            return max(
                max(maxSubArrayHelper(nums, l, m), maxSubArrayHelper(nums, m+1, h)),
                maxSubArrayCrossed(nums, l, m, h));
        }
        
    public:    
        int maxSubArray(vector<int>& nums) {
            return maxSubArrayHelper(nums, 0, nums.size()-1);
        }
    };
    

    Complexity Analysis

    • Time complexity :

      The time complexity can be expressed as the following recursive relation:
      $$T(n) = 2T(n/2) + Θ(n)$$, as we are dividing the problem of size n into 2 subproblems each of size n/2 and combining them in back in Θ(n).

      The above recursive relation is similar to the merge sort and has a worst case time complexity as $$Θ(nlogn)$$ using Master method.

    • Space complexity : $$O(n)$$ which is the recursion space.


    Approach #3 Single traversal [Accepted]

    Algorithm

    The approach is to compute the maximum sum while doing the single traversal of the vector.

    Keep track of the sum we have got sofar and if the current element is greater than the sum, update the sum and during the process, keep updating the max.

    C++

    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            int max = INT_MIN, sum = 0;
            for(const auto &n: nums) {
                sum +=n;
                if(sum < n)
                    sum = n;
                if(max < sum) 
                    max = sum;
            }
            return max;
        }
    };
    

    Complexity Analysis

    • Time complexity : $$O(n)$$ as we are visiting each element once.

    • Space complexity : $$O(1)$$ as we are not using any additional variable space.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.