Java: 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(int[] nums) {
        
        int sz = nums.length;
        int priorState = nums[0];
        int ans = nums[0];

        // To calculate current ans, if we need just one or two prior elements
        // then we don't need to create an array. We can just use one/two variable to store
        // previous states.[ in DP]
        for(int i=1;i<nums.length;i++){

            if(nums[i]+ priorState > nums[i])
                priorState = nums[i]+priorState;
            else
                priorState = nums[i];

            ans = Math.max(ans,priorState);
        }
        return ans;
    }
}

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!