“给定一个整数数组,找到最大和的连续子数组,返回其最大和。”
题目链接:
来源:力扣(LeetCode)
链接:53. 最大子序和 - 力扣(LeetCode) (leetcode-cn.com)
给定一个整数数组 nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例 1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例 2:
输入: nums = [1]
输出: 1
这个题解法很多,可以使用暴力法、动态规划、贪心法、分治法。
这里就用动态规划法来解这道题。
假设数组的长度是n,下标是0到n-1,f(i)代表连续子数组的最大和,那么只需要求出每个位置的f(i),不就找到最大和了吗?
那么怎么求每个位置的f(i)呢?这取决于nums[i]和f[i-1]+nums[i]谁更大,所以就可以推到出动态规划转移方程:
f(i)=max{f(i-1)+nums[i],nums[i]}
代码参考:
public class Solution {
public int MaxSubArray(int[] nums) {
int pre = 0, maxAns = nums[0];
foreach (int x in nums) {
pre = Math.Max(pre + x, x);
maxAns = Math.Max(maxAns, pre);
}
return maxAns;
}
}
时间复杂度 : O(n)
其中n是数组的长度,只需要遍历一遍数组即可求得答案。
空间复杂度: O(1)
只需要常数级别的空间存放变量。
我觉得这道题目的思想是:
走完这一生
如果我和你在一起会变得更好,那我们就在一起,否则我就丢下你。
我回顾我最光辉的时刻
就是和不同人在一起,变得更好的最长连续时刻