Maximum Subarray

Problem Statement

LeetCode-53: Given an integer array nums, find the sub-array with the largest sum, and return its sum.

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.

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

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

Approach

We can use Kadane’s algorithm to solve this problem. The algorithm is based on the following idea:

1. We traverse the array while maintaining a local sum currentSum for the maximum subarray ending at each index.
2. At each step, we decide whether to extend the existing subarray or start fresh from the current element.

The decision to extend the existing array or not is done by comparing the current element with the sum of the current element and the previous subarray i.e. $currentSum=max(nums[i],currentSum+nums[i])$

If currentSum+nums[i] is greater than nums[i], it means extending the current subarray is beneficial. On the other hand nums[i] itself is larger, then the previous subarray’s sum is hurting the result, so we start fresh. Additionally,the algorithm keeps track of the maximum sum encountered so far.

Consider the example: [-2,1,-3,4,-1,2,1,-5,4]

Here is the step-by-step approach to solve the problem:

1. Initialize two variables maxSum and currentSum to nums[0].
2. Iterate over the array starting from index 1.
3. For each element num in the array:
   • Update currentSum to the maximum of num and currentSum + num.
   • Update maxSum to the maximum of maxSum and currentSum.
   • Continue the iteration.
4. Return maxSum.

This also handles an edge case where all the elements in the array are negative. In this case, the algorithm will return the maximum element in the array.

Implementation

Here is a Java implementation of the above approach:

public int maxSubArray(int[] nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];

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

    return maxSum;
}

Complexity Analysis

The time complexity for this approach is $O(n)$, where $n$ is the length of the input array nums. The space complexity is $O(1)$ since we use only a constant amount of extra space.