Maximum profit by buying and selling a share at most K times | Greedy Approach | Java program to find out maximum profit by buying and selling a share at most k times given the stock price of n days ; Function to return the maximum profit ; Find the farthest decreasing span of prices before prices rise ; Find the farthest increasing span of prices before prices fall again ; Check if the current buying price is greater than that of the previous transaction ; Store the profit ; Remove the previous transaction ; Check if the current selling price is less than that of the previous transactions ; Store the new profit ; Remove the previous transaction ; Add the new transactions ; Finally store the profits of all the transactions ; Add the highest K profits ; Return the maximum profit ; Driver code
import java . util . * ; import java . lang . * ; class GFG { static int maxProfit ( int n , int k , int prices [ ] ) { int ans = 0 , buy = 0 , sell = 0 ; Stack < int [ ] > transaction = new Stack < > ( ) ; PriorityQueue < Integer > profits = new PriorityQueue < > ( ) ; while ( sell < n ) { buy = sell ; while ( buy < n - 1 && prices [ buy ] >= prices [ buy + 1 ] ) buy ++ ; sell = buy + 1 ; while ( sell < n && prices [ sell ] >= prices [ sell - 1 ] ) sell ++ ; while ( ! transaction . isEmpty ( ) && prices [ buy ] < prices [ transaction . peek ( ) [ 0 ] ] ) { int [ ] p = transaction . peek ( ) ; profits . add ( prices [ p [ 1 ] - 1 ] - prices [ p [ 0 ] ] ) ; transaction . pop ( ) ; } while ( ! transaction . isEmpty ( ) && prices [ sell - 1 ] > prices [ transaction . peek ( ) [ 1 ] - 1 ] ) { int [ ] p = transaction . peek ( ) ; profits . add ( prices [ p [ 1 ] - 1 ] - prices [ buy ] ) ; buy = p [ 0 ] ; transaction . pop ( ) ; } transaction . push ( new int [ ] { buy , sell } ) ; } while ( ! transaction . isEmpty ( ) ) { profits . add ( prices [ transaction . peek ( ) [ 1 ] - 1 ] - prices [ transaction . peek ( ) [ 0 ] ] ) ; transaction . pop ( ) ; } while ( k > 0 && ! profits . isEmpty ( ) ) { ans += profits . peek ( ) ; profits . poll ( ) ; -- k ; } return ans ; } public static void main ( String [ ] args ) { int k = 3 ; int prices [ ] = { 1 , 12 , 10 , 7 , 10 , 13 , 11 , 10 , 7 , 6 , 9 } ; int n = prices . length ; System . out . println ( " Maximum ▁ profit ▁ is ▁ " + maxProfit ( n , k , prices ) ) ; } }