algoadvance

Leetcode 53. Maximum Subarray

Problem Statement

Given an integer array nums, find the contiguous subarray (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: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Constraints:

Clarifying Questions

  1. Can the array contain both positive and negative integers?
    • Yes, as seen in the example.
  2. Should subarrays be contiguous?
    • Yes, subarrays should be contiguous.
  3. Can the array be as small as one element?
    • Yes, the problem states the minimal length can be 1.

Strategy

We can solve this problem using Kadane’s Algorithm which is designed to solve the maximum subarray sum problem efficiently. Here is the approach:

  1. Initialize two variables:
    • current_sum: This tracks the sum of the current subarray we are considering.
    • max_sum: This keeps track of the maximum sum encountered so far.
  2. Iterate through the array:
    • Update current_sum to be either the current element itself or the sum of the current element and the previous current_sum, whichever is greater. This decision reconnects to the idea of starting a new subarray at the current element if the previous subarray sum is negative.
    • Update max_sum to be the maximum value between the current max_sum and current_sum.
  3. Return max_sum as the result, which should be the maximum sum of any contiguous subarray.

Time Complexity

The time complexity for Kadane’s Algorithm is O(n), where n is the length of the input array nums. This is because we only make a single pass through the array.

The space complexity is O(1) since we are using a constant amount of extra space.

Code

Here is the C++ implementation of the strategy detailed above:

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxSubArray(std::vector<int>& nums) {
        int max_sum = nums[0];
        int current_sum = nums[0];
        
        for(size_t i = 1; i < nums.size(); ++i) {
            current_sum = std::max(nums[i], current_sum + nums[i]);
            max_sum = std::max(max_sum, current_sum);
        }
        
        return max_sum;
    }
};

Explanation of the Code

  1. Initialize max_sum and current_sum to the first element of the array.
  2. Iterate from the second element to the end of the array:
    • Update current_sum to the maximum of the current element or the sum of current_sum + current element.
    • Update max_sum to be the maximum of max_sum and current_sum.
  3. Return max_sum, which holds the maximum sum of any contiguous subarray.

This approach efficiently finds the maximum sum of a contiguous subarray with a single pass through the input array.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI