贪心算法
思路：核心是找到prediff和curdiff，每次遍历i过程中，这两个数需要一正一负或一负一正，符号相反，
此为局部最优，如果上述条件成立则result++，不断累加。
注：如[2,3]时，遍历没有prediff只有curdiff，因此将其看作[2,2,3]，意思其实是让prediff=0可以通过，
就是刚开始的时候需要注意。此外，这个题解配合prediff=curdiff赋值的位置，刚好解决了中间两数相等的问题，
如[2,5,3,3,4]，中间两个3，如果每次遍历i都prediff=curdiff赋值，则条件prediff=0时会出问题，因为
遍历到“平”的时候（curdiff=0不会进prediff=0会进）就进入了if，实际是不能进入的。
注：此题搭配图解看理解更佳，P310。
1：题干表示，少于2个元素为摆动序列
2：size=2个元素起步，result从1开始算，如果只2个元素，则[2,3]会进if返回2，[2,2]不会进if返回1
3：i和i+1遍历，注意i<size-1，不是平时的i<size
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() <= 1) return nums.size(); // wyh 1
int curdiff = 0, prediff = 0;
int result = 1; // wyh 2
for (int i = 0; i < nums.size() - 1; i++) { // wyh 3
curdiff = nums[i + 1] - nums[i];
if ((curdiff > 0 && prediff <= 0) || (curdiff < 0 && prediff >= 0)) {
result++;
prediff = curdiff; // 这个地方必须放在判断里面，否则放外面会出问题，如[2,5,3,3,1]
// 当出现下坡-平路-下坡时，本身是始终不能result++的，如果放外面则会出现平路-下坡时result++
// 即：↘↗ or →↗ or ↗↘ or →↘都是可以的，但↗→ or ↘→是不行的。
// 如果此时不行但给prediff赋值了，后续形成了↗→↗ or ↘→↘，本不该result++就会导致result++。
}
}
return result;
}
};
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() <= 1) return nums.size();
vector<int> dp(nums.size(), 1);
// dp[0] = 1;
if (nums[0] != nums[1]) dp[1] = 2;
for (int i = 2; i < nums.size(); i++) {
if (nums[i - 2] <= nums[i - 1] && nums[i - 1] > nums[i] ||
nums[i - 2] >= nums[i - 1] && nums[i - 1] < nums[i]) {
dp[i] = dp[i - 1] + 1;
} else {
dp[i] = dp[i - 1];
}
}
for (auto &v : dp) {
cout<<v<<" ";
}
return dp[nums.size() - 1];
}
};
// 普通例子
[1,3,6,5,7,8]
[1 2 2 3 4 4]
[1,6,5,7]
// 特殊例子
[3 3 3 2 5]
[1 1 1 1 2]
// 下述案例无法通过
[372,492,288,399,81,2,320,94,416,469,427,117,265,357,399,456,496,337,355,219,475,295,457,350,490,470,281,127,131,36,430,412,442,174,128,253,1,56,306,295,340,73,253,130,259,223,14,79,409,384,209,151,317,441,156,275,140,224,128,250,290,191,161,472,477,125,470,230,321,5,311,23,27,248,138,284,215,356,320,194,434,136,221,273,450,440,28,179,36,386,482,203,24,8,391,21,500,484,135,348,292,396,145,443,406,61,212,480,455,78,309,318,84,474,209,225,177,356,227,263,181,476,478,151,494,395,23,114,395,429,450,247,245,150,354,230,100,172,454,155,189,33,290,187,443,123,59,358,241,141,39,196,491,381,157,157,134,431,295,20,123,118,207,199,317,188,267,335,315,308,115,321,56,52,253,492,97,374,398,272,74,206,109,172,471,55,452,452,329,367,372,252,99,62,122,287,320,325,307,481,316,378,87,97,457,21,312,249,354,286,196,43,170,500,265,253,19,480,438,113,473,247,257,33,395,456,246,310,469,408,112,385,53,449,117,122,210,286,149,20,364,372,71,26,155,292,16,72,384,160,79,241,346,230,15,427,96,95,59,151,325,490,223,131,81,294,18,70,171,339,14,40,463,421,355,123,408,357,202,235,390,344,198,98,361,434,174,216,197,274,231,85,494,57,136,258,134,441,477,456,318,155,138,461,65,426,162,90,342,284,374,204,464,9,280,391,491,231,298,284,82,417,355,356,207,367,262,244,283,489,477,143,495,472,372,447,322,399,239,450,168,202,89,333,276,199,416,490,494,488,137,327,113,189,430,320,197,120,71,262,31,295,218,74,238,169,489,308,300,260,397,308,328,267,419,84,357,486,289,312,230,64,468,227,268,28,243,267,254,153,407,399,346,385,77,297,273,484,366,482,491,368,221,423,107,272,98,309,426,181,320,77,185,382,478,398,476,22,328,450,299,211,285,62,344,484,395,466,291,487,301,407,28,295,36,429,99,462,240,124,261,387,30,362,161,156,184,188,99,377,392,442,300,98,285,312,312,365,415,367,105,81,378,413,43,326,490,320,266,390,53,327,75,332,454,29,370,392,360,1,335,355,344,120,417,455,93,60,256,451,188,161,388,338,238,26,275,340,109,185]
1 2 3 4 5 5 6 7 8 8 9 9 10 10 10 10 10 11 12 13 14 15 16 17 18 19 19 19 20 21 22 23 24 25 25 26 27 28 28 29 30 31 32 33 34 35 35 36 36 37 37 37 38 38 39 40 41 42 43 44 44 45 45 46 46 47 48 49 50 51 52 53 54 54 55 56 57 58 59 59 60 61 62 62 62 63 63 64 65 66 66 67 67 67 68 69 70 71 71 72 73 74 75 76 77 77 78 78 79 79 80 80 81 82 83 84 85 86 87 88 89 90 90 91 92 93 93 94 94 94 94 95 95 95 96 97 97 98 98 99 100 101 102 103 104 105 105 106 107 107 107 108 108 109 109 109 110 111 112 112 113 114 115 116 117 118 119 119 120 120 120 121 122 122 123 123 124 125 125 126 126 127 128 129 129 130 131 131 132 133 133 134 134 134 135 135 135 135 136 137 138 139 140 141 141 142 143 144 145 146 146 146 147 147 148 148 148 149 150 150 151 152 153 154 155 155 156 157 157 158 158 159 160 161 162 163 163 163 164 164 165 165 166 166 167 167 168 169 169 170 170 171 171 172 172 173 174 174 174 175 175 175 176 176 176 177 178 179 179 179 180 181 181 182 182 182 183 184 184 185 185 186 186 186 187 187 188 189 190 191 192 192 193 194 195 195 196 197 197 198 198 198 198 199 200 201 202 202 203 204 205 206 207 208 209 209 209 210 211 212 212 213 214 215 216 217 218 218 219 219 220 220 221 222 222 223 224 225 226 227 228 229 230 231 232 232 233 233 233 234 234 235 236 237 237 238 238 238 238 239 240 241 242 242 243 244 245 246 246 246 247 248 249 250 251 252 253 253 254 255 256 256 257 258 259 260 261 261 262 262 263 264 264 265 266 267 268 269 270 271 271 272 272 273 274 275 276 277 277 278 279 280 281 281 281 282 283 284 285 285 286 286 287 288 289 289 290 291 292 293 294 295 296 297 298 299 300 301 302 302 303 303 304 305 306 306 307 307 308 309 309 309 310 310 311 311 311 312 312 313 313 313 314 314 315 316 316 317 317 318 319 320 321 322 322 323 324 324 325 325 326 326 327 327 328 328 329 329 330 330 331 331 332 333 333 333 334 334 335 336