AlgoPressAppearance
42-连续子数组的最大和
题目描述
https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为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/
思路1，双指针同时移动，模拟运算
csharp
public class Solution {
//思路 ： 复杂度为 O(n) 说明只能循环一次，因为要求连续子数组的和，所以应该是双指针法
public int MaxSubArray(int[] nums) {
if(nums.Length == 0){
return 0;
}
if(nums.Length == 1){
return nums[0];
}
int p1 = 0;
int p2 = 1;
int currentSum = nums[0];
int maxSum = currentSum;
while(p1 < p2 && p2 < nums.Length){
//计算右指针
currentSum+=nums[p2];
//计算左指针(排除负数)
if(nums[p1] < 0){
currentSum-=nums[p1];
p1+=1;
}
//如果当前和小于最后一个数
if(currentSum < nums[p2]){
p1 = p2;
currentSum = nums[p2];
}
if(currentSum > maxSum){
maxSum = currentSum;
}
p2+=1;
}
return maxSum;
}
}
思路2：动态规划
动态规划最主要的是状态转移方程
dp数组存储计算到每一次的最大值，每次计算的值都放进去，留作下一次比较
dp[i] = Math.Max(dp[i-1] + nums[i], nums[i])
这部分是最重要的部分， 当前的最大值，应该是前面能计算出来的最大值，和当前的值比较，如果前面所有的和还比这个数小，则选择目前的数，否则就是累计起来的值为最大。
csharp
// 思路 ：动态规划 从第一步开始计算
public int MaxSubArray(int[] nums) {
if(nums.Length == 1){
return nums[0];
}
int[] dp = new int[nums.Length];
dp[0] = nums[0]; // dp 中存储的就是目前为止的最大值
int maxValue = dp[0];
for(int i = 1; i < nums.Length; i++){
dp[i] = Math.Max(dp[i-1] + nums[i], nums[i]);
if(maxValue < dp[i]){
maxValue = dp[i];
}
}
return maxValue;
}
复习
csharp
public class Solution {
public int MaxSubArray(int[] nums) {
int sum = 0;
int max = -101;
for(int i=0; i<nums.Length; i++ ){
sum += nums[i];
if(sum < nums[i]){
sum = nums[i];
}
max = Math.Max(sum,max);
}
return max;
}
}