42. 连续子数组的最大和

本文主要是介绍42. 连续子数组的最大和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

comments: true
difficulty: 简单
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9842.%20%E8%BF%9E%E7%BB%AD%E5%AD%90%E6%95%B0%E7%BB%84%E7%9A%84%E6%9C%80%E5%A4%A7%E5%92%8C/README.md

面试题 42. 连续子数组的最大和

题目描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

 

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

 

提示：

• 1 <= arr.length <= 10^5
• -100 <= arr[i] <= 100

注意：本题与主站 53 题相同：https://leetcode.cn/problems/maximum-subarray/

 

解法

方法一：动态规划

我们定义 $f[i]$ 表示以第 $i$ 位数结尾的「连续子数组的最大和，【注意这种 以第i位结尾 的定义方式】那么很显然我们要求的答案就是：

$$\underset{0\le i\le n-1}{\max }f[i]$$

那么我们如何求 $f[i]$ 呢？我们可以考虑 $nums[i]$ 单独成为一段还是加入 $f[i-1]$ 对应的那一段，这取决于 $nums[i]$ 和 $f[i-1]+nums[i]$ 哪个大，我们希望获得一个比较大的，于是可以写出这样的状态转移方程：

$$f[i]=\max (f[i-1]+nums[i],nums[i])$$

或者可以写成这样：

$$f[i]=\max (f[i-1],0)+nums[i]$$

我们可以不用开一个数组来存储所有的计算结果，而是只用两个变量 $f$ 和 $ans$ 来维护对于每一个位置 $i$ 我们的最大值，这样我们可以省去空间复杂度的开销。

时间复杂度 $O(n)$，其中 $n$ 为数组长度。空间复杂度 $O(1)$。

Python3

class Solution:def maxSubArray(self, nums: List[int]) -> int:ans, f = -inf, 0for x in nums:f = max(f, 0) + x #核心：如果连续区间和不大于0就要考虑新的区间起始ans = max(ans, f)#找所有区间和中最大的return ans

Java

class Solution {public int maxSubArray(int[] nums) {int ans = Integer.MIN_VALUE;int f = 0;for (int x : nums) {f = Math.max(f, 0) + x;ans = Math.max(ans, f);}return ans;}
}

C++

class Solution {
public:int maxSubArray(vector<int>& nums) {int ans = INT_MIN;int f = 0;for (int& x : nums) {f = max(f, 0) + x;ans = max(ans, f);}return ans;}
};

Go

func maxSubArray(nums []int) int {ans, f := -1000000000, 0for _, x := range nums {f = max(f, 0) + xans = max(ans, f)}return ans
}

TypeScript

function maxSubArray(nums: number[]): number {let res = nums[0];for (let i = 1; i < nums.length; i++) {nums[i] = Math.max(nums[i], nums[i - 1] + nums[i]);res = Math.max(res, nums[i]);}return res;
}

Rust

impl Solution {pub fn max_sub_array(mut nums: Vec<i32>) -> i32 {let mut res = nums[0];for i in 1..nums.len() {nums[i] = nums[i].max(nums[i - 1] + nums[i]);res = res.max(nums[i]);}res}
}

JavaScript

/*** @param {number[]} nums* @return {number}*/
var maxSubArray = function (nums) {let ans = -1e10;let f = 0;for (const x of nums) {f = Math.max(f, 0) + x;ans = Math.max(ans, f);}return ans;
};

C#

public class Solution {public int MaxSubArray(int[] nums) {int ans = -1000000000;int f = 0;foreach (int x in nums) {f = Math.Max(f, 0) + x;ans = Math.Max(ans, f);}return ans;}
}

Swift

class Solution {func maxSubArray(_ nums: [Int]) -> Int {var ans = Int.minvar currentSum = 0for x in nums {currentSum = max(currentSum, 0) + xans = max(ans, currentSum)}return ans}
}

这篇关于42. 连续子数组的最大和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---