|
1
2
3
4
5
6
|
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
Subscribe to see which companies asked this question.
|
题意：股票的买入卖出。你只有两次机会买入卖出。
|
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
|
public
class
Solution {
public
int
maxProfit(
int
[] prices) {
if
(prices==
null
|| prices.length<
2
)
return
0
;
//O(n^2)哎
int
sum=
0
;
for
(
int
i=
1
;i<prices.length;i++){
int
temp=getMax(prices,
0
,i)+getMax(prices,i+
1
,prices.length-
1
);
if
(temp>sum)sum=temp;
}
return
sum;
}
public
static
int
getMax(
int
[] prices,
int
left,
int
right){
if
(left>=prices.length)
return
0
;
int
Min=prices[left];
int
sum=
0
;
for
(
int
i=left+
1
;i<=right;i++){
Min=Math.min(Min,prices[i]);
sum=Math.max(sum,prices[i]-Min);
}
System.out.println(sum);
return
sum;
// }
// //first[i]从左往右遍历，表示到第i天时卖出能赚到的最大钱
// int[] first=new int[prices.length];
// //second[i]从右往左遍历，表示从第i天到最后一天能赚到的最大钱。本质还是分两部分计算。只不过是分开两次扫描数组
// int[] second=new int[prices.length];
// int min=prices[0];
// for(int i=1;i<prices.length;i++){
// min=Math.min(min,prices[i]);
// first[i]=Math.max(first[i-1],prices[i]-min);
// }
// // for(int i=0;i<prices.length;i++){
// // System.out.println(first[i]);
// // }
// int max=prices[prices.length-1];
// for(int i=prices.length-2;i>=0;i--){
// max=Math.max(max,prices[i]);
// second[i]=Math.max(second[i+1],max-prices[i]);
// }
// int ret=0;
// for(int i=0;i<prices.length;i++){
// //System.out.println(second[i]);
// ret=Math.max(first[i]+second[i],ret);
// }
// return ret;
}
}
|
PS:解法一是直接以第i天为界，求两边的最大收益。但是需要O(N^2)。
优化：用俩数组，遍历两次。
本文转自 努力的C 51CTO博客，原文链接:http://blog.51cto.com/fulin0532/1910811
