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 idea that a subarray with the largest sum ending at index i either includes the subarray with the largest sum ending at index i-1 or starts from index i.

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.