Buy And Sell Stocks - Two Transactions Allowed

 1. You are given a number n, representing the number of days.

2. You are given n numbers, where ith number represents price of stock on ith day.

3. You are required to print the maximum profit you can make if you are allowed two transactions at-most.

Note - There can be no overlapping transaction. One transaction needs to be closed (a buy followed by a sell) before opening another transaction (another buy).

Input Format

A number n

.. n more elements

Output Format

A number representing the maximum profit you can make if you are allowed a single transaction.

Constraints

0 <= n <= 20

0 <= n1, n2, .. <= 10

Sample Input

9

11

6

7

19

4

1

6

18

4

Sample Output

30

Solution

import java.io.*;

import java.util.*;

public class Main {

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

        // write your code here

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] A = new int[n];

        for(int i=0;i<n;i++)

            A[i] = sc.nextInt();

        

        int dp[][] = new int[n][2];

        dp[0][0] = 0;

        int min = A[0], profit = 0;

        for(int i=1;i<n;i++){

            profit = Math.max(profit,A[i]-min);

            if(A[i]<min)

                min = A[i];

            dp[i][0] = profit;

        }

       

        dp[n-1][1] = 0;

        int max = A[n-1];

        profit = 0;

        for(int i=n-2;i>=0;i--){

            profit = Math.max(profit,max-A[i]);

            if(A[i]>max)

                max = A[i];

            dp[i][1] = profit;

        }

        

        int sum = 0;

        for(int i=0;i<n;i++)

            sum = Math.max(sum, dp[i][0]+dp[i][1]);

        

        System.out.println(sum);

    }

}