Maximum Subarray medium

Problem Statement

Find the contiguous subarray within an array (containing at least one number) which has the largest sum and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Steps:

The problem can be efficiently solved using Kadane's Algorithm. The algorithm iterates through the array, keeping track of the current maximum sum and the overall maximum sum.

1. Initialization:

   • currentMax: Starts at the first element of the array. This variable tracks the maximum sum ending at the current position.
   • overallMax: Starts at the first element of the array. This variable tracks the global maximum sum found so far.

2. Iteration:

   • For each element in the array:
     • Update currentMax: currentMax becomes the maximum of the current element and the sum of the current element and the previous currentMax. This essentially decides whether to start a new subarray at the current element or extend the existing one.
     • Update overallMax: overallMax is updated to the maximum of overallMax and currentMax. This ensures we always keep track of the largest sum encountered.

3. Return:

   • After iterating through the entire array, overallMax will hold the maximum contiguous subarray sum.

Explanation:

Kadane's Algorithm cleverly avoids the need for nested loops (which would lead to O(n^2) complexity). By efficiently updating currentMax at each step, it dynamically determines whether extending the current subarray or starting a new one leads to a larger sum. The overallMax variable ensures we keep track of the best sum found so far.

Code:

class Solution {
    public int maxSubArray(int[] nums) {
        int currentMax = nums[0];
        int overallMax = nums[0];

        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            overallMax = Math.max(overallMax, currentMax);
        }

        return overallMax;
    }
}

Complexity:

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array only once.
• Space Complexity: O(1). We use only a constant amount of extra space to store currentMax and overallMax.