**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**

- Find
in maximum value on which share can be sell.

Largest element in the right current element.
- If
there is any profit to sell the share add it the PROFIT.
- Repeat
the step#1 and step#2.

Time
complexity: O(n^2).

Space complexity:
O(1).

**Solution#2: Dynamic
Programming.**

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

- To
find maximum earn to buy a share:

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

**Values[]:**

**MaxArray[]:**

Maximum
element from right to left.

**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 {

BufferedReader
reader = new BufferedReader(

new InputStreamReader(System.*in*));

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

for(int
i=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**