Buy And Sell Stocks With Transaction Fee - Infinite 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 give a number fee, representing the transaction fee for every transaction.

4. You are required to print the maximum profit you can make if you are allowed infinite transactions, but has to pay "fee" for every closed transaction.

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

A number fee

Output Format

A number representing the maximum profit you can make if you are allowed infinite transactions with transaction fee.

Constraints

0 <= n <= 20

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

0 <= fee <= 5

Sample Input

12

10

15

17

20

16

18

22

20

22

20

23

25

3

Sample Output

13

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 chrg = sc.nextInt();

        

        

        int bp = 0, sp = 0, bbp = 0, ssp= 0;

        bbp -= A[0];

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

            bp = Math.max(bbp, ssp - A[i]);

            sp = Math.max(ssp, A[i]-chrg+bbp);

            bbp = bp;

            ssp = sp;

        }

        

        System.out.println(Math.max(bbp,ssp));

    }

}