AlgoPressAppearance
0053-最大子数组和
https://leetcode.cn/problems/maximum-subarray
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组[4,-1,2,1] 的和最大，为6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
思路1：动态规划
最大和的连续子数组，(最值问题考虑动态规划) 定义 dp 数组， dp[i] 表示到i处最大的连续子数组的和，那么 dp[i] = max(dp[i-1]+nums[i],nums[i]) 因为要连续子数组，所以前面的和加上当前的数 和 当前数字作比较，如果当前数字大于所有的和，那么舍弃前面的数字。 反之则保留
参考代码
csharp
public class Solution{
public int MaxSubArray(int[] nums){
//试试动态规划
//定义dp数组， dp[i] 表示到i位置最大连续子数组的和
// dp[i] = max(dp[i-1] + nums[i],nums[i])
int[] dp = new int[nums.Length];
dp[0] = nums[0];
int max = dp[0];
for(int i=1; i<nums.Length; i++){
dp[i] = Math.Max(dp[i-1]+nums[i],nums[i]);
max = Math.Max(dp[i],max);
}
return max;
}
}
优化空间复杂度 Kadane 解法
因为每次计算的时候之和前面一次计算结果相关，所以可以省略dp的数组，直接记录前一次
csharp
public class Solution{
public int MaxSubArray(int[] nums){
int maxSum = nums[0];
int maxEndingHere = nums[0];
for(int i=1;i<nums.Length;i++){
maxEndingHere= Math.Max(maxEndingHere+nums[i],nums[i]);
maxSum = Math.Max(maxEndingHere,maxSum);
}
return maxSum;
}
}
贪心算法
贪心算法的思路和前面优化空间后的动规是一样的。
总体思路就是，从一开始就累加当前和，当发现累加的当前和是负数的时候，那说明前面累计的和没有作用，不如舍去，从0开始，即从下一个数开始从新技术。
csharp
public class Solution{
public int MaxSubArray(int[] nums){
int curSum = 0;
int maxSum = int.MinValue;
for(int i=0; i<nums.Length; i++){
curSum+=nums[i];
maxSum = Math.Max(curSum,maxSum);
curSum = Math.Max(0,curSum);
}
return maxSum;
}
}
复习贪心:20220514
csharp
public class Solution {
public int MaxSubArray(int[] nums) {
int curSum = nums[0];
int maxSum = curSum;
for(int i=1; i<nums.Length; i++){
curSum = Math.Max(nums[i],curSum+nums[i]);
maxSum = Math.Max(maxSum,curSum);
}
return maxSum;
}
}