问道leetcode上的题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问道leetcode上的题

问道leetcode上的题# JobHunting - 待字闺中

j*n2012-05-30 07:05

1 楼

http://www.leetcode.com/2010/11/best-time-to-buy-and-sell-stock
下面有人给了个新问题：
if you can keep buying and selling, how to maximize the profit? for example,
if it is 6,1,3,2,4,7, we can buy for 1 and sell for 3, and we can buy for 2
, and sell for 4,then buy on 4, sell for 7. total maxval =3-1+4-2+7-4 = 7.
They would like to have some O(n) solutions.

j*n2012-05-30 07:05

2 楼

顶一顶

Z*Z2012-05-30 07:05

3 楼

最直白的算法不行么？
public class Stock{
public static void main(String[] args){
int[] arr = {6,1,3,2,4,7};
System.out.println(stock(arr));
}
static int stock(int[] 股票){
assert(股票 != null && 股票.length > 0);
int 我的钱 = 0;
int 低点 = 股票[0];
for(int i = 0; i < 股票.length; i ++){
if(股票[i] <= 低点){
低点 = 股票[i];
} else if(i == 股票.length - 1 || i < 股票.length - 1 &
& 股票[i+1] < 股票[i]){
//要跌了，赶紧卖
我的钱 += 股票[i] - 低点;
低点 = 股票[i];
}
}
return 我的钱;
}
}

【在 j*****n 的大作中提到】

: 顶一顶

s*r2012-05-30 07:05

4 楼

为什么我觉得LS的程序很有喜感

j*n2012-05-30 07:05

5 楼

但这并不maximize啊

【在 Z*****Z 的大作中提到】

: 最直白的算法不行么？
: public class Stock{
: public static void main(String[] args){
: int[] arr = {6,1,3,2,4,7};
: System.out.println(stock(arr));
: }
: static int stock(int[] 股票){
: assert(股票 != null && 股票.length > 0);
: int 我的钱 = 0;
: int 低点 = 股票[0];

j*e2012-05-30 07:05

6 楼

把这些点画在图上，用线连起来，可以看到交替的上升和下降阶段，
只要你抓住所有的上升阶段，必然maximize收益。
所以，只要发现转折为下降（第二天比第一天低），就卖
发现转折为上升，就买

example,
2

【在 j*****n 的大作中提到】

: http://www.leetcode.com/2010/11/best-time-to-buy-and-sell-stock
: 下面有人给了个新问题：
: if you can keep buying and selling, how to maximize the profit? for example,
: if it is 6,1,3,2,4,7, we can buy for 1 and sell for 3, and we can buy for 2
: , and sell for 4,then buy on 4, sell for 7. total maxval =3-1+4-2+7-4 = 7.
: They would like to have some O(n) solutions.

j*n2012-05-30 07:05

7 楼

您老的code太难看了。。。不过好像是对的，和下面这个同修的意思一样。

【在 Z*****Z 的大作中提到】