## Tuesday, 8 December 2015

### 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.
L
argest 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:
p
rofit = 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.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
public static void main(String[] args) throws Exception {

for(int i=0;i<count;i++) {
int[] values = new int[ip_size];
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