给你一组天的股票价格。每天,您可以购买一个单位的股票,出售您已经购买的任意数量的股票单位,或者什么也不做。通过优化交易策略,您可以获得的最大利润是多少?
示例(输入,即天数可能会有所不同)
5 3 2 => profit = 0 // since the price decreases each day ,the max profit we can make = 0
1 2 100 => profit = 197
1 3 1 2 =>profit = 3 // we buy at 1 sell at 3 , then we buy at 1 and sell at 2 ..total profit = 3
我的解决方案听起来与给出的答案完全相同,但由于某种原因,我的算法没有为某些大型测试用例返回正确答案。任何人都可以看到我的代码有问题吗?
public class StockMax {
private static final int BUY = 1;
private static final int SELL = 0;
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Scanner stdin = new Scanner(System.in);
//int T;
//T = stdin.nextInt();
//while (T-- > 0) {
int N;
int[] price;
int[] opt;
N = stdin.nextInt();
price = new int[N];
opt = new int[N];
for (int i = 0; i < N; i++) {
price[i] = stdin.nextInt();
}
opt[N - 1] = SELL;
for (int i = N - 1; i > 0; i--) {
if (price[i - 1] < price[i]) {
opt[i - 1] = BUY;
} else {
opt[i - 1] = SELL;
}
}
int own, profit, cost;
own = profit = cost = 0;
for (int i = 0; i < N; i++) {
if (opt[i] == BUY) {
own++;
cost += price[i];
} else {
profit += ((own * price[i]) - cost);
cost = own = 0;
}
}
System.out.println(profit);
}
}
这是我在下面的评论中提到的代码的更新版本。我仍然失败了更多的测试用例然后通过了。
import java.util.Scanner;
public class StockMax {
private static final int BUY = 1;
private static final int SELL = 0;
private static int glb_max;
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Scanner stdin = new Scanner(System.in);
int T;
T = stdin.nextInt();
while (T-- > 0) {
int N;
int[] price;
int[] opt;
N = stdin.nextInt();
price = new int[N];
opt = new int[N];
for (int i = 0; i < N; i++) {
price[i] = stdin.nextInt();
}
opt[N - 1] = SELL;
glb_max = price[N - 1];
for (int i = N - 1; i > 0; i--) {
if (price[i - 1] <= glb_max ) {
opt[i - 1] = BUY;
} else {
opt[i - 1] = SELL;
glb_max = price[i - 1];
}
}
/*
for(int i = 0; i < N;i++){
System.out.print(opt[i] + " ");
}
*/
int own, profit, cost;
own = profit = cost = 0;
for (int i = 0; i < N; i++) {
if (opt[i] == BUY) {
own++;
cost += price[i];
} else {
profit += ((own * price[i]) - cost);
cost = own = 0;
}
}
System.out.println(profit);
}
}
}