Welcome to Subscribe On Youtube
53. Maximum Subarray
Description
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
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Solutions
Solution 1: Dynamic Programming
We define $f[i]$ to represent the maximum sum of the continuous subarray ending with the element $nums[i]$. Initially, $f[0] = nums[0]$. The final answer we are looking for is $\max_{0 \leq i < n} f[i]$.
Consider $f[i]$, where $i \geq 1$, its state transition equation is:
\[f[i] = \max \{ f[i - 1] + nums[i], nums[i] \}\]Which is also:
\[f[i] = \max \{ f[i - 1], 0 \} + nums[i]\]Since $f[i]$ is only related to $f[i - 1]$, we can use a single variable $f$ to maintain the current value of $f[i]$, and then perform state transition. The answer is $\max_{0 \leq i < n} f$.
The time complexity is $O(n)$, where $n$ is the length of the array $nums$. We only need to traverse the array once to get the answer. The space complexity is $O(1)$, we only need constant space to store several variables.
Solution 2
This implementation uses bit manipulation. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.
-
class Solution { public int maxSubArray(int[] nums) { int ans = nums[0]; for (int i = 1, f = nums[0]; i < nums.length; ++i) { f = Math.max(f, 0) + nums[i]; ans = Math.max(ans, f); } return ans; } } // Solution 2 class Solution { public int maxSubArray(int[] nums) { return maxSub(nums, 0, nums.length - 1); } private int maxSub(int[] nums, int left, int right) { if (left == right) { return nums[left]; } int mid = (left + right) >>> 1; int lsum = maxSub(nums, left, mid); int rsum = maxSub(nums, mid + 1, right); return Math.max(Math.max(lsum, rsum), crossMaxSub(nums, left, mid, right)); } private int crossMaxSub(int[] nums, int left, int mid, int right) { int lsum = 0, rsum = 0; int lmx = Integer.MIN_VALUE, rmx = Integer.MIN_VALUE; for (int i = mid; i >= left; --i) { lsum += nums[i]; lmx = Math.max(lmx, lsum); } for (int i = mid + 1; i <= right; ++i) { rsum += nums[i]; rmx = Math.max(rmx, rsum); } return lmx + rmx; } } -
class Solution { public: int maxSubArray(vector<int>& nums) { int ans = nums[0], f = nums[0]; for (int i = 1; i < nums.size(); ++i) { f = max(f, 0) + nums[i]; ans = max(ans, f); } return ans; } }; -
class Solution: def maxSubArray(self, nums: List[int]) -> int: res = cur_sum = nums[0] for num in nums[1:]: cur_sum = num + max(cur_sum, 0) res = max(res, cur_sum) return res # Solution 2 class Solution: def maxSubArray(self, nums: List[int]) -> int: def crossMaxSub(nums, left, mid, right): lsum = rsum = 0 lmx = rmx = -inf for i in range(mid, left - 1, -1): lsum += nums[i] lmx = max(lmx, lsum) for i in range(mid + 1, right + 1): rsum += nums[i] rmx = max(rmx, rsum) return lmx + rmx def maxSub(nums, left, right): if left == right: return nums[left] mid = (left + right) >> 1 lsum = maxSub(nums, left, mid) rsum = maxSub(nums, mid + 1, right) csum = crossMaxSub(nums, left, mid, right) return max(lsum, rsum, csum) left, right = 0, len(nums) - 1 return maxSub(nums, left, right) -
func maxSubArray(nums []int) int { ans, f := nums[0], nums[0] for _, x := range nums[1:] { f = max(f, 0) + x ans = max(ans, f) } return ans } -
function maxSubArray(nums: number[]): number { let [ans, f] = [nums[0], nums[0]]; for (let i = 1; i < nums.length; ++i) { f = Math.max(f, 0) + nums[i]; ans = Math.max(ans, f); } return ans; } -
/** * @param {number[]} nums * @return {number} */ var maxSubArray = function (nums) { let [ans, f] = [nums[0], nums[0]]; for (let i = 1; i < nums.length; ++i) { f = Math.max(f, 0) + nums[i]; ans = Math.max(ans, f); } return ans; }; -
public class Solution { public int MaxSubArray(int[] nums) { int ans = nums[0], f = nums[0]; for (int i = 1; i < nums.Length; ++i) { f = Math.Max(f, 0) + nums[i]; ans = Math.Max(ans, f); } return ans; } } -
impl Solution { pub fn max_sub_array(nums: Vec<i32>) -> i32 { let n = nums.len(); let mut ans = nums[0]; let mut f = nums[0]; for i in 1..n { f = f.max(0) + nums[i]; ans = ans.max(f); } ans } }