grid47 Exploring patterns and algorithms
Nov 1, 2024
5 min read
Solution to LeetCode 53: Maximum Subarray Problem
Given an integer array nums, find the contiguous subarray (containing at least one number) that has the largest sum and return its sum.
Problem
Approach
Steps
Complexity
Input: The input consists of a single integer array `nums`.
Example: ["nums = [3, -2, 5, -1, 2]"]
Constraints:
• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
Output: The output should be a single integer, which is the largest sum of a contiguous subarray in the input array `nums`.
Example: ["8"]
Constraints:
• The sum of the subarray is guaranteed to be a valid integer.
Goal: The goal is to find the subarray with the maximum sum using an optimal solution.
Steps:
• 1. Initialize two variables: `l` for the current subarray sum and `g` for the maximum sum found so far.
• 2. Iterate through the array and update `l` based on whether adding the current number increases the sum or not.
• 3. Update `g` to track the maximum subarray sum encountered during the iteration.
• 4. Return the value of `g`.
Goal: The input consists of an integer array `nums`.
Steps:
• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
Assumptions:
• The array `nums` will always contain at least one element.
• The solution needs to handle arrays with both positive and negative numbers.
• Input: ["nums = [3, -2, 5, -1, 2]"]
• Explanation: In this example, the largest sum subarray is `[3, -2, 5, -1, 2]`, which gives a sum of `8`.
• Input: ["nums = [-3, 4, -1, 2, 1]"]
• Explanation: Here, the largest sum subarray is `[4, -1, 2, 1]`, which gives a sum of `6`.
Approach: The approach uses a dynamic programming technique to find the largest sum subarray in linear time.
Observations:
• We can compute the maximum subarray sum efficiently by keeping track of the current sum and updating the maximum sum found so far.
• Kadane's Algorithm is the ideal approach to solve this problem in O(n) time.
Steps:
• 1. Initialize two variables, `l` and `g`, where `l` keeps track of the current subarray sum and `g` keeps track of the global maximum sum.
• 2. Iterate through the `nums` array, updating `l` by either adding the current element or starting a new subarray from the current element.
• 3. At each step, update `g` to hold the maximum of `g` and `l`.
• 4. Return the value of `g` after iterating through the entire array.
Empty Inputs:
• The problem guarantees that the array will have at least one element.
Large Inputs:
• The solution must handle inputs with up to 10^5 elements efficiently.
Special Values:
• When all elements are negative, the solution should return the largest (least negative) number.
Constraints:
• The algorithm needs to work efficiently for both small and large arrays.
intmaxSubArray(vector<int>& nums) {
int l = nums[0], g = nums[0];
for(int i =1; i < nums.size(); i++) {
if(nums[i] > l + nums[i])
l = nums[i];
else l += nums[i];
g = max(g, l);
}
return g;
}
1 : Function Declaration
intmaxSubArray(vector<int>& nums) {
This line declares a function named `maxSubArray` that takes a vector of integers `nums` as input and returns the maximum sum of a contiguous subarray.
2 : Variable Initialization
int l = nums[0], g = nums[0];
This line initializes two integer variables: `l` to store the sum of the current contiguous subarray and `g` to store the global maximum sum. Both are initialized to the first element of the `nums` array.
3 : Iterate Over Array
for(int i =1; i < nums.size(); i++) {
This loop iterates over the elements of the `nums` array, starting from the second element.
4 : Check for New Subarray
if(nums[i] > l + nums[i])
This condition checks if starting a new subarray at the current element `nums[i]` would yield a larger sum than continuing the previous subarray.
5 : Start New Subarray
l = nums[i];
If the condition is true, the current element `nums[i]` becomes the new starting point for the subarray, and `l` is updated to its value.
6 : Continue Current Subarray
else l += nums[i];
If the condition is false, it's more beneficial to continue the current subarray, so the current element `nums[i]` is added to the current sum `l`.
7 : Update Global Maximum
g = max(g, l);
The global maximum sum `g` is updated to the maximum of its current value and the current subarray sum `l`.
8 : Return Global Maximum
return g;
After iterating through the entire array, the function returns the final global maximum sum `g`, which represents the maximum sum of any contiguous subarray.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The algorithm iterates through the array exactly once, making the time complexity O(n).
Best Case: O(1)
Worst Case: O(1)
Description: The solution uses a constant amount of space, so the space complexity is O(1).
