25. Maximum profit by buying and selling a share at most twice

25. Maximum profit by buying and selling a share at most twice

Problem link :- click here

package programs;

import java.util.*;

public class Array__25
{

	static int maxProfitByByuingOrSellingSharesAtMostTwice(int price[], int n)
	{
		//as our idea is do one transaction from end and other from start
		//we need a array to keep updating the maximum profit
		int profit[] = new int[n];
		
		//lets initialize last element as zero as my     1st transaction is from end
		//you can make first element as zero if your 1st transaction is from beginning
		profit[n-1] = 0;
		
		/*1st TRANSACTION FROM END
		    you have to store max if your transaction is from end
		    since you are moving to left & you should sell shares to your right but you don't know the value
		    and you will get more profit when the price is maximum while selling
		    hence you are storing maximum element to your right*/
		int max = price[n-1];
		//starting iteration from 2nd last element as you cannot buy and sell the share in the same day
		for(int i=n-2; i>=0; i--)
		{
			//update maximum
			if(price[i] > max)
				max = price[i];
			
			/*update profit
			    max-price[i]   --->
			                       means you buy shares in 'i' day and sell it in future
			   you know future of the shares-value as price is already given*/
			profit[i] = Math.max(profit[i+1], max-price[i]);
		}
		//END OF 1st TRANSACTION
		//by the end you will have the maximum profit in 'profit[0]'
		
		/*2nd TRANSACTION FROM BEGINNING
		    similarly as 1st transaction, here we have to store minimum
		    because you are buying the shares when the value is minimum*/
		int min = price[0];
		for(int i=1; i<n; i++)
		{
			//update minimum 
			if(price[i] < min)
				min = price[i];
			
			/*update profit
			    price[i]-min ---> profit of this transaction
			    NOTE :- you should update it with last transaction*/
			profit[i] = Math.max(   profit[i-1], profit[i]+  (price[i]-min)    );
		}
		//END OF 2nd TRANSACTION
		//by the end of 2nd transaction you will have the maximum profit in 'profit[n-1]'
		
		return profit[n-1];
	}
	
	public static void main(String[] args)
	{
		int i, n, ans;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the size of the array : ");
		n = s.nextInt();
		int array[] = new int[n];
		System.out.println("Enter the elements of the array : ");
		for(i=0; i<n; i++)
			array[i] = s.nextInt();
		
		System.out.println("Given Array : ");
		print_array(array);
		
		ans = maxProfitByByuingOrSellingSharesAtMostTwice(array, n);
		System.out.println("\n\nMaximum profit in atmost 2 transaction is :  " + ans);
	}

	static void print_array(int arr[])
	{
		for(int i=0; i<arr.length; i++)
			System.out.print(arr[i] + " ");
	}
}

Time complexity :- O(n)
space complexity :- O(n)