1

给你一组天的股票价格。每天，您可以购买一个单位的股票，出售您已经购买的任意数量的股票单位，或者什么也不做。通过优化交易策略，您可以获得的最大利润是多少？

示例（输入，即天数可能会有所不同）

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);

        }
    }
}
4

3 回答 3

2

要测试这样的算法，您可以尝试编写一个蛮力测试器，尝试所有买入/卖出决策并测量可实现的最大利润。

我怀疑用这个蛮力测试器测试你当前的算法即使在一些小测试用例上也会出现问题。

示例 1

2 2 2 2 4

当前算法选择在价格保持不变的情况下卖出，因此在此示例中只会获得 2 利润。

示例 2

2 3 4 1 100

当前的算法在价格下跌时出售所有东西，因此将以价格 4 出售所有东西，而不是等待价格 100。

更好的算法

从最后一天开始倒推。

跟踪您未来见过的最优惠价格。

如果当前价格低于未来的最佳价格，则购买。

如果当前价格优于未来的最优价格，则全部卖出。

否则，什么也不做。

于 2013-06-02T20:53:46.640 回答
2

我刚刚在一个竞赛网站上解决了这个问题。我会给你一个我的算法的基本概念，

1. smax = maximum stock price from the list
2. then find the profit by assuming you have bought all the stocks till smax 
   and you sell it at the price of smax
3. then check if smax is the last element of the stock price list 
   if yes then return profit as answer, 
   if no 
   then make a new list containing stock prices after smax to the last stock price
   and repeat steps 1-3 and keep adding profit of each iteration to get the final profit.
于 2013-06-03T22:22:39.097 回答
0

这是一个递归解决方案。

public class BuysOrSellStocks {
    public static void main(String[] args) {
        int[] arr = {1,2,4,1,3};
        int profit = findProfit(0, arr.length, arr, 0);
        System.out.println("Final profit = "+ profit);
    }

    private static int findProfit(int start, int end, int[] arr, int profit) {
        if(start > arr.length-1)
            return profit;
        else {
            int maxIndex = findMaxIndex(arr, start, end-1);
            int noOfShares = 0;
            while(start<maxIndex) {
                profit = profit - arr[start];
                noOfShares++;
                start++;
            }
            profit = profit + (arr[maxIndex] * noOfShares);
            return findProfit(++maxIndex, end, arr, profit);
        }
    }

    private static int findMaxIndex(int[] arr, int start, int end) {
        int maxVal = Integer.MIN_VALUE;
        int maxInd = 0;
        for(int i=start; i<=end; i++)
            if(arr[i]>maxVal) {
                maxVal = arr[i];
                maxInd=i;
            }
        return maxInd;
    }
}
于 2018-06-06T17:44:10.393 回答