Maximizing profit for given stock quotes, my solution in java

1
votes

You are given the stock prices for a set of days . Each day, you can either buy one unit of stock, sell any number of stock units you have already bought, or do nothing. What is the maximum profit you can obtain by planning your trading strategy optimally?

Examples ( The input i.e the no of days can vary ) 

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

My solution sounds exactly like the answer given but for some reason my algorithm is not returning the correct answer for some large test cases . Can anybody see a problem with my code ?

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

This is the updated version of my code as mentioned in my comments below. I still fail more test cases then pass.

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

        }
    }
}
3
javaalgorithmdynamic-programming
Welcome to Stack Overflow! Asking people to spot errors in your code is not especially productive. You should use the debugger (or add print statements) to isolate the problem, by tracing the progress of your program, and comparing it to what you expect to happen. As soon as the two diverge, then you've found your problem. (And then if necessary, you should construct a minimal test-case.) – Oliver Charlesworth
I should probably include the original problem instead or just referencing another thread sorry, like I said its my first thread on this site. – user2445793
The question : You are given the stock prices for a set of days . Each day, you can either buy one unit of stock, sell any number of stock units you have already bought, or do nothing. What is the maximum profit you can obtain by planning your trading strategy optimally? Examples ( The input i.e the no of days can vary ) 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 – user2445793
Its not so much errors I would like to know if their is a general flaw in my algorithm. I have tested it on smaller test cases and its works. But for test cases that are impossibly large to test out manually i seem to get wrong answer. – user2445793
JUnit and debugger. Once you have some unit tests post the failing tests. – Adam Gent

3 Answers

2
votes

To test an algorithm like this you could try writing a brute force tester that tried all buy/sell decisions and measured the maximum profit achievable.

I suspect that testing your current algorithm with this brute force tester would turn up problems even on some small test cases.

Example 1

2 2 2 2 4

The current algorithm chooses to sell if the price remains constant so will make only 2 profit on this example.

Example 2

2 3 4 1 100

The current algorithm sells everything whenever the price decrease, so will sell everything at price 4, instead of waiting for price 100.

Better algorithm

Work backwards from the last day.

Keep track of the best price you have ever seen in the future.

Buy if the current price is less than the best price in the future.

Sell all if the current price is better than the best price in the future.

Otherwise, do nothing.

2
votes

I just solved that problem in a contest site. I will give you a basic idea of my algorithm,

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.
0
votes

Here's a recursive solution.

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