C++: Maximum Subarray

Thought Process

The Maximum Subarray problem requires finding the contiguous subarray with the largest sum. The key idea is to decide whether to extend the current subarray or start a new subarray at each step. Here's how it works:

Initialize maxSum with the first element of the array. Iterate through the array starting from the second element. For each element, decide whether adding it to the previous subarray sum i.e. nums[i-1] is beneficial or not. If the sum of the current element and the previous subarray sum is greater than the current element itself, update the current element to this sum. Otherwise, keep as it is. Simultaneously, keep track of the maximum sum encountered during the iteration & return the maximum value. 

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        
        int maxSum = nums[0];
        for(int i=1;i<nums.size();i++){

            // If taking previous element is profitable to
            // current element then take it else leave it.
            if(nums[i] + nums[i-1] > nums[i])
                nums[i] = nums[i] + nums[i-1];

            if(nums[i]>maxSum)
                maxSum = nums[i];
        }
        return maxSum;
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the array once, making it linear in time complexity.

Space Complexity: O(1)

The algorithm uses a constant amount of extra space, regardless of the input size.

Code copied!