这个题我真心没想到我竟然独立AC了，中间过程好曲折啊。所以坚持就是胜利。
题意大致是：
买股票，只能有一次买卖的机会。问你在某天买，之后的某天卖，请问如何获得最大的收益。
我擦，我想这个多简单，我直接暴力不就行了。
果然呵呵了。TLE
后来想破脑子的想啊，怎么降低时间复杂度啊。
快排啊？
贪心啊？觉得和2sum问题很像，特别是画了竖直线以后。
后来一下。。。咦。。。天与天之间是有高度差的。如果求出这个差，然后求出连续子序列最大和。这个问题不就解决了？
抱着试一试的心态，我去~~~AC啦 阿和~
附上代码：
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
|
class Solution {
public:
int maxProfit(vector<int> &prices) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int max = 0;
if(prices.size() <= 1)
return max;
vector<int> dis(prices.size()-1);
for(int i = 1;i < prices.size();i++) {
dis[i-1] = prices[i] - prices[i-1];
}
vector<int> value(dis.size());
for(int i = 0;i < dis.size();i++) {
value[i] = dis[i];
}
if(dis[0] < 0)
value[0] = 0;
else
value[0] = dis[0];
for(int i = 1;i < value.size();i++) {
if(value[i-1] + value[i] < 0) {
value[i] = 0;
} else {
value[i] = value[i-1] + value[i];
}
}
for(int i = 0;i < value.size();i++) {
if(value[i] > max) {
max = value[i];
}
}
return max;
}
};
|