关于leetcode:每日一练22连续子数组的最大和

title: 每日一练（22）：间断子数组的最大和

categories:[剑指 offer]

tags:[每日一练]

date: 2022/02/21

每日一练（22）：间断子数组的最大和

输出一个整型数组，数组中的一个或间断多个整数组成一个子数组。求所有子数组的和的最大值。

要求工夫复杂度为 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

起源：力扣（LeetCode）

链接：https://leetcode-cn.com/probl…

办法一：前缀和

思路和算法

1. 都是正数的状况下 每次都是 sum 为以后值，顺次与 maxsum 比拟取其中最大的。
2. 失常状况下（有正有负）累计前缀和，只有 sum 大于 0（还有存在价值），就加上来，判断与后面的 maxsum 谁大，取较大值；
3. 以后和变小到 0 时（阐明后面的正数对消了，前面来的数不论是正是负，后面累计的和 0 都没价值了），则从新从以后数开始，同时保障子数组的连续性。
4. 留神不是遇到正数就从新赋值。另外须要不停的判断以后和是不是最大的。

int maxSubArray(vector<int>& nums) {int maxSum = nums[0];    // 默认第一个数为最大值
    int sum = 0;
    for (int i = 0; i < nums.size(); i++) {sum = sum <= 0 ? nums[i] : sum + nums[i];// 以后和不大于 0 时，阐明后面对消了，从新开始累计和; 同样的如果都是正数时，则顺次比拟哪个最大，赋值给 maxSum
        maxSum = sum > maxSum ? sum : maxSum;            // 不停比拟更新 maxSum
    }
    return maxSum;
}

办法二：动静布局（DP 方程）

思路和算法

最原始的动静布局

• 状态:dp[i]: 以第 i 个数结尾的和的最大值
• 转移: 若 dp[i – 1] < 0, 则以第 i 个数结尾的和的最大值为第 i 个数自身
• 若 dp[i – 1] > 0, 则以第 i 个数结尾的和的最大值为的 dp[i – 1] 与 dp[i – 1] + nums[i] 中的较大者
• 防止遍历 dp 数组，每次比拟 dp 更新完结后比拟 res 与 dp[i] 的大小作为返回值

int maxSubArray(vector<int>& nums) {int len = nums.size();
    vector<int> dp(len);
    dp[0] = nums[0];
    int res = nums[0];
    for (int i = 1; i < len; i++) {
        // 判断
        if(dp[i - 1] > 0) {dp[i] = max(dp[i - 1] + nums[i], nums[i]);
        } else {dp[i] = nums[i];
        }
        // 三目运算符
        //dp[i] = (dp[i - 1] > 0) ? dp[i] = max(dp[i - 1] + nums[i], nums[i]) : nums[i];
        res = max(res, dp[i]);
    }
    return res;
}