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 a contiguous subarray ending at element nums[i]. Initially, f[0] = nums[0]. The final answer we seek is max_{0 ≤ i < n} f[i].
Consider f[i] for i ≥ 1. Its state transition equation is:
$$
f[i] = \max(f[i - 1] + \textit{nums}[i], \textit{nums}[i])
$$
That is:
$$
f[i] = \max(f[i - 1], 0) + \textit{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 perform the state transition. The answer is max_{0 ≤ i < n} f.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
PythonJavaC++GoTypeScriptRustJavaScriptC#
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
ans = f = nums[0]
for x in nums[1:]:
f = max(f, 0) + x
ans = max(ans, f)
return ans(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
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
}
}(code-box)
/**
* @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;
};(code-box)
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;
}
}(code-box)
Solution 2
PythonJava
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)(code-box)
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;
}
}(code-box)
