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

Stock Buy Sell for Maximum Profit

The cost of a stock on a day is given in a list, find the max profit that we can make by buying and selling once.

Example:

If the given array is {90, 170, 700, 300, 30, 525, 685}.

Maximum profit: 685 – 30.

90

170

700

300

30

525

685

Solution:

90

170

700

300

30

525

685

minArray[]: Minimum element in left sub-array of every index.

90

90

90

90

30

30

30

maxArray[]: Maximum element in right sub-array of every index.

700

700

700

685

685

685

685

difference[]: Difference of minArray[i]-maxArray[i].

610

610

610

595

655

655

655

Maximum value in difference array will be treated as result.

Tape Equilibrium

TapeEquilibrium

Minimize the value |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])|.

A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape.

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

In other words, it is the absolute difference between the sum of the first part and the sum of the second part.

For example

consider array A such that:

  A[0] = 3

  A[1] = 1

  A[2] = 2

  A[3] = 4

  A[4] = 3

We can split this tape in four places:

P = 1, difference = |3 − 10| = 7

P = 2, difference = |4 − 9| = 5

P = 3, difference = |6 − 7| = 1

P = 4, difference = |10 − 3| = 7

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.

For example, given:

  A[0] = 3

  A[1] = 1

  A[2] = 2

  A[3] = 4

  A[4] = 3

the function should return 1, as explained above.

Assume that:

N is an integer within the range [2..100,000];

each element of array A is an integer within the range [−1,000..1,000].

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Solution:

class Solution {

    public int solution(int[] A) {

       

        int len = A.length;

        if(len==1) {

            return Math.abs(A[0]);

        } else if(len==2) {

            return Math.abs((A[0]-A[1]));

        }

        double sum = 0;

        for(int val : A) {

            sum = sum+val;

        }

        double leftSum = 0, difference = 0, minimum = Integer.MAX_VALUE;

        for(int i=0; i<len-1; i++) {

            leftSum = leftSum + A[i];

            difference = sum - 2*leftSum;

           

            minimum = Math.min(Math.abs(difference), minimum);

        }

        return (int) minimum;

    }

}

Check my submission:

https://codility.com/demo/results/trainingJJUXQ9-2FK/