Problem 16 - Maximum Subarray

Explore our archive for previous posts.

Question

Given an integer array nums, find the subarray with 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.

Constraints:

• 1 <= nums.length <= 105

• -104 <= nums[i] <= 104

Approach

In this solution, we use the Kadane's algorithm to find the maximum subarray sum. We initialize two variables, maxSum and currentSum, as the first element of the input array. We then traverse the array starting from the second element.

For each element, we calculate the maximum between the current element itself and the sum of the current element and the currentSum. This step allows us to determine whether to start a new subarray or extend the current subarray.

We update the maxSum if the currentSum is greater. This ensures that we keep track of the maximum subarray sum encountered so far.

Finally, we return the maxSum, which represents the maximum sum of any subarray in the given array.

Solution

Solve it here

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0]; // Initialize maxSum as the first element
        int currentSum = nums[0]; // Initialize currentSum as the first element

        // Traverse the array starting from the second element
        for (int i = 1; i < nums.length; i++) {
            // Calculate the maximum between the current element and the sum of the current element and currentSum
            currentSum = Math.max(nums[i], currentSum + nums[i]);

            // Update the maximum sum if the currentSum is greater
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }
}

Time and space complexity

Time Complexity: The time complexity of the above solution is O(N), where N is the length of the input array. This is because we iterate through the array once to calculate the maximum subarray sum. Each element is visited and processed once, resulting in a linear time complexity.

Space Complexity: The space complexity of the solution is O(1) since we only use a constant amount of extra space. We maintain two variables, maxSum and currentSum, to track the maximum subarray sum and the current sum. No additional data structures or arrays are used, and the space usage remains constant regardless of the input size.