Maximum profit by buying and selling a share at most K times | Greedy Approach | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxProfit ( int n , int k , int prices [ ] ) { int ans = 0 , buy = 0 , sell = 0 ; stack < pair < int , int > > transaction ; priority_queue < int > profits ; 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 . empty ( ) && prices [ buy ] < prices [ transaction . top ( ) . first ] ) { pair < int , int > p = transaction . top ( ) ; profits . push ( prices [ p . second - 1 ] - prices [ p . first ] ) ; transaction . pop ( ) ; } while ( ! transaction . empty ( ) && prices [ sell - 1 ] > prices [ transaction . top ( ) . second - 1 ] ) { pair < int , int > p = transaction . top ( ) ; profits . push ( prices [ p . second - 1 ] - prices [ buy ] ) ; buy = p . first ; transaction . pop ( ) ; } transaction . push ( { buy , sell } ) ; } while ( ! transaction . empty ( ) ) { profits . push ( prices [ transaction . top ( ) . second - 1 ] - prices [ transaction . top ( ) . first ] ) ; transaction . pop ( ) ; } while ( k && ! profits . empty ( ) ) { ans += profits . top ( ) ; profits . pop ( ) ; -- k ; } return ans ; } int main ( ) { int k = 3 ; int prices [ ] = { 1 , 12 , 10 , 7 , 10 , 13 , 11 , 10 , 7 , 6 , 9 } ; int n = sizeof ( prices ) / sizeof ( prices [ 0 ] ) ; cout << " Maximum ▁ profit ▁ is ▁ " << maxProfit ( n , k , prices ) ; return 0 ; }