1

一連の日の株価が表示されます。毎日、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. 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 に答える