一个是连续的，lintcode的原题。。。算是dp吧。。。无聊。。。
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 | class Solution {
public:
/**
* @param A an array of Integer
* @return an integer
*/
int longestIncreasingContinuousSubsequence(vector<int>& A) {
// Write your code here
int n=A.size();
if (n<=1)
return n;
int beg=1;
int result=INT_MIN;
int end=1;
for (int i=1; i<n; i++){
if (A[i]>A[i-1]){
beg++;
result=max(beg,result);
}
else
beg=1;
}
for (int i=n-2; i>=0; i--){
if (A[i]>A[i+1]){
end++;
result=max(end,result);
}
else
end=1;
}
return result;
}
};
|
另外一个是无排序的。。。这个用hash来做。。。
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 | class Solution {
public:
/**
* @param nums: A list of integers
* @return an integer
*/
int longestConsecutive(vector<int> &num) {
// write you code here
int m=1;
unordered_set<int> set;
for (int i=0; i<num.size(); i++)
set.insert(num[i]);
for (int i=0; i<num.size(); i++){
int up=num[i];
int down=num[i]-1;
while(set.find(up)!=set.end()){
set.erase(up++);
}
while(set.find(down)!=set.end()){
set.erase(down--);
}
m=max(m, up-down-1);
}
return m;
}
};
|
No comments:
Post a Comment