Maximize the Stock profit

Problem Statement

Design algorithms to predicting the maximum profit when you know what the share price of ORANGE FT Group will be for the next N days.

Conditions:

1. You can either buy one share of ORANGE FT Group each day.

2. You can sell any number/no share of shares of Orange owned by you.

What is the maximum profit you can obtain with an optimum trading strategy?

Input

First line: Number of test cases.

Second line: Number of days.

Third line: Share value on particular day.

Output

Maximum profit of each day.

Solution#1: Brute force

1. Find in maximum value on which share can be sell.
   Largest element in the right current element.
2. If there is any profit to sell the share add it the PROFIT.
3. Repeat the step#1 and step#2.

Time complexity: O(n^2).

Space complexity: O(1).

Solution#2: Dynamic Programming.

1. Find out the maximum value of the right side of index and keep update the value in maxArr [] till zero index.
   maxArr[i] = Math.max(maxArr[i+1], values[i]);
   
2. To find maximum earn to buy a share:
   profit = profit + Math.max(maxArr[r]-values[r],0);

Values[]:

10

20

30

40

50

MaxArray[]:

Maximum element from right to left.

50

50

50

50

50

profit = profit + Math.max(maxArr[r]-values[r],0);

Time complexity: O(n).

Space complexity: O(n).

import java.io.*;

importjava.util.*;

importjava.text.*;

importjava.math.*;

importjava.util.regex.*;

public class Solution {

     public static voidmain(String[] args) throws Exception {

           BufferedReader reader = new BufferedReader(

                                 new InputStreamReader(System.in));

           int count = Integer.parseInt(reader.readLine());

           for(inti=0;i<count;i++) {

                int ip_size = Integer.parseInt(reader.readLine());

                int[] values = new int[ip_size];

                String valStr = reader.readLine();

                int j = 0;

                for(String el : valStr.split(" ")) {

                     values[j] = Integer.parseInt(el);

                     j++;

                }

                int[] maxArr = new int[values.length];

                maxArr[values.length-1] = values[values.length-1];

                int q = values.length-2;

                while(q>=0) {

                     maxArr[q] = Math.max(maxArr[q+1],values[q]);

                     q--;

                }

                long profit = 0;

                for(int r=0;r<ip_size;r++) {

                     profit = profit +

                          Math.max(maxArr[r]-values[r],0);

                }

                System.out.println(profit);

           }

     }

}

Input:

1

5

10 20 30 40 50

Output:

100

Reference

https://www.hackerrank.com/challenges/stockmax