如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例:
1
2
3
4
5
6
7
8
9
10
| 输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列就是一个摆动序列。
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 它的几个子序列满足摆动序列。其中一个是[1,17,10,13,10,16,8]。
输入: [1,2,3,4,5,6,7,8,9]
输出: 2
|
思路
f(n)=max{f(0)+n,f(1)+n,…,f(n-1)+n};
f(n)表示以n结尾的最大的个数。
o(n*n)
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| class Solution {
public int wiggleMaxLength(int[] a) {
int l=a.length;
Item[] items = new Item[l];
int re =0;
for(int i=0;i<l;i++){
Item item= new Item();
if(i==0){
item.num=1;
item.needBig=2;
}else{
int max=0;
int nb=0;
int temp =a[i];
for(int j=0;j<i;j++){
int number=1;
int t=a[j];
int temp1=items[j].num;
int b = items[j].needBig;
if(temp>t){
if(b==0){
number=2;
if(number>max){
max=number;
nb=0;
}
}else if(b==1){
number=temp1+1;
if(number>max){
max=number;
nb=0;
}
}else {
number=2;
if(number>max){
max=number;
nb=0;
}
}
}else if(temp==t){
number=1;
if(number>max){
max=number;
nb=2;
}
}else{
if(b==0){
number=temp1+1;
if(number>max){
max=number;
nb=1;
}
}else if(b==1){
number=2;
if(number>max){
max=number;
nb=1;
}
}else{
number=2;
if(number>max){
max=number;
nb=1;
}
}
}
}
item.num=max;
item.needBig=nb;
}
items[i]=item;
re=re>item.num?re:item.num;
System.out.println(item.num+" "+item.needBig);
}
return re;
}
class Item{
int num;
int needBig;
}
}
|