# 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.

• 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;
}
}

• 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


• 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
}
}