376. 摆动序列
说实话，没明白为啥算是贪心。
最开始的思路是去重，然后统计正负变化次数。
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size()==1) return 1;
int ans=0,last=-2,now;
for(int i=1; i<nums.size(); i++)
{
// 忽略连续的重复元素
if(nums[i] == nums[i-1]) continue;
// 判断当前正还是负
now= (nums[i] - nums[i-1]) > 0 ? 1 : -1;
// 判断方向是否发生变化，若变化，则累计变化次数(折线数)
if(now!=last) ans++;
// 更新上一次方向
last=now;
}
//到最后的节点，算上该节点，所以++
return ++ans;
}
};后面看了题解，挺多是按照动态规划解的，暂时还不会，卡哥这个题解也挺好的，这个解法不用去重，省下了一个o(n)的时间
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size() == 1) return 1;
if(nums.size() == 2 && nums[0] != nums[1]) return 2;
int diff1 = nums[1] - nums[0];
int diff2 = 0;
int result = diff1 != 0 ? 2 : 1;
for(int i = 2; i < nums.size(); i++){
diff2 = nums[i] - nums[i-1];
if((diff1 <= 0 && diff2 > 0) || (diff1 >= 0 && diff2 < 0)){
result++;
diff1 = diff2;
}
}
return result;
}
};53. 最大子序和
这题暴力解法的思路，第一层 for 就是设置起始位置，第二层 for 循环遍历数组寻找最大值。
暴力是O(n^2)的，为了降低时间复杂度，回看题目，连续数组的问题，尝试滑动窗口，滑动窗口其实就是双指针的应用之一，是有效的将 n^2 降到 n 的方法。再看题目，求某个子数组的和，联想到了前缀和，然后联想到之前用前缀数组+滑动窗口的解题方法，考虑这题也这么用。但这题存在负值，无法保证单调性，用滑动窗口维护非常困难，或者说就是滑不了。所以放弃使用滑动窗口，想想怎么使用前缀和。
使用前缀和数组能快速得出 i，j 的区间和，num[ j ] - num[ i ]，即可得出区间 i, j 的和。使用前缀和数组，我们就可以将寻找最大和的连续子数组的问题转换成在前缀和数组中，寻找 i, j （i < j）区间下标，使得区间的和最大，即将原来的问题转换成了，寻找前缀和数组中的最小值，以及最大值，两者的差就是区间和。
这种思路的思考过程是由于知道前缀和的技巧才能联想到，没了解过前缀和是比较难联想到的。
后续看题解学习的过程中，发现有相同思路但并不需要构造前缀和数组方法。直接在构造前缀和的过程中维护最小值和最大值即可，不需要用数组将前缀和存储起来，这样减少了空间复杂度。
class Solution {
public:
int maxSubArray(vector<int> &nums) {
int ans = INT_MIN;
int min_pre_sum = 0;
int pre_sum = 0;
for (int x : nums) {
pre_sum += x; // 当前的前缀和
ans = max(ans, pre_sum - min_pre_sum); // 减去前缀和的最小值
min_pre_sum = min(min_pre_sum, pre_sum); // 维护前缀和的最小值
}
return ans;
}
};
题目有提到进阶的要求，使用分治来处理这个问题。
这里记录一下卡哥的思路，这个我确实想不到。如何用贪心来解，分析如下：
贪心贪的是哪里呢？
如果 -2 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是贪心贪的地方！
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。
从代码角度上来讲：遍历 nums，从头开始用 count 累积，如果 count 一旦加上 nums[i]变为负数，那么就应该从 nums[i+1]开始从 0 累积 count 了，因为已经变为负数的 count，只会拖累总和。
这相当于是暴力解法中的不断调整最大子序和区间的起始位置。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int result = INT32_MIN;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
count += nums[i];
if (count > result) { // 取区间累计的最大值（相当于不断确定最大子序终止位置）
result = count;
}
if (count <= 0) count = 0; // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
}
return result;
}
};常见误区
误区一：
不少同学认为 如果输入用例都是-1，或者 都是负数，这个贪心算法跑出来的结果是 0， 这是又一次证明脑洞模拟不靠谱的经典案例，建议大家把代码运行一下试一试，就知道了，也会理解 为什么 result 要初始化为最小负数了。
误区二：
大家在使用贪心算法求解本题，经常陷入的误区，就是分不清，是遇到 负数就选择起始位置，还是连续和为负选择起始位置。
在动画演示用，大家可以发现， 4，遇到 -1 的时候，我们依然累加了，为什么呢？
因为和为 3，只要连续和还是正数就会 对后面的元素 起到增大总和的作用。 所以只要连续和为正数我们就保留。
这里也会有录友疑惑，那 4 + -1 之后 不就变小了吗？ 会不会错过 4 成为最大连续和的可能性？
其实并不会，因为还有一个变量 result 一直在更新 最大的连续和，只要有更大的连续和出现，result 就更新了，那么 result 已经把 4 更新了，后面 连续和变成 3，也不会对最后结果有影响。
卡哥：“本题的贪心思路其实并不好想，这也进一步验证了，别看贪心理论很直白，有时候看似是常识，但贪心的题目一点都不简单！”
这下放心了，确实不好想，不是我笨，哈哈哈
标签：count,前缀,nums,int,随想录,455,53,result,数组 From： https://blog.csdn.net/xl1052524603/article/details/139548015