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