j*****n
发帖数: 1545 | 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*****n
发帖数: 1545 | | Z*****Z
发帖数: 723 | 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********r
发帖数: 277 | | j*****n
发帖数: 1545 | 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********e
发帖数: 1192 | 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*****n
发帖数: 1545 | 7 您老的code太难看了。。。 不过好像是对的， 和下面这个同修的意思一样。
【在 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];
| l*********8
发帖数: 4642 | 8 难道这就是用传说中的中文编程语言写的 ：）
【在 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];
|
|
