Maximum profit by buying and selling a share at most K times | Greedy Approach | 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
def maxProfit ( n , k , prices ) : NEW_LINE INDENT ans = 0 NEW_LINE buy = 0 NEW_LINE sell = 0 NEW_LINE transaction = [ ] NEW_LINE profits = [ ] NEW_LINE while ( sell < n ) : NEW_LINE INDENT buy = sell NEW_LINE while ( buy < n - 1 and prices [ buy ] >= prices [ buy + 1 ] ) : NEW_LINE INDENT buy += 1 NEW_LINE DEDENT sell = buy + 1 NEW_LINE while ( sell < n and prices [ sell ] >= prices [ sell - 1 ] ) : NEW_LINE INDENT sell += 1 NEW_LINE DEDENT while ( len ( transaction ) != 0 and prices [ buy ] < prices [ transaction [ len ( transaction ) - 1 ] [ 0 ] ] ) : NEW_LINE INDENT p = transaction [ len ( transaction ) - 1 ] NEW_LINE profits . append ( prices [ p [ 1 ] - 1 ] - prices [ p [ 0 ] ] ) NEW_LINE transaction . remove ( transaction [ len ( transaction ) - 1 ] ) NEW_LINE DEDENT profits . sort ( reverse = True ) NEW_LINE while ( len ( transaction ) != 0 and prices [ sell - 1 ] > prices [ transaction [ len ( transaction ) - 1 ] [ 1 ] - 1 ] ) : NEW_LINE INDENT p = transaction [ len ( transaction ) - 1 ] NEW_LINE profits . append ( prices [ p [ 1 ] - 1 ] - prices [ buy ] ) NEW_LINE buy = p [ 0 ] NEW_LINE transaction . remove ( transaction [ len ( transaction ) - 1 ] ) NEW_LINE DEDENT transaction . append ( [ buy , sell ] ) NEW_LINE DEDENT profits . sort ( reverse = True ) NEW_LINE while ( len ( transaction ) != 0 ) : NEW_LINE INDENT profits . append ( prices [ transaction [ len ( transaction ) - 1 ] [ 1 ] - 1 ] - prices [ transaction [ len ( transaction ) - 1 ] [ 0 ] ] ) NEW_LINE transaction . remove ( transaction [ len ( transaction ) - 1 ] ) NEW_LINE DEDENT profits . sort ( reverse = True ) NEW_LINE while ( k != 0 and len ( profits ) != 0 ) : NEW_LINE INDENT ans += profits [ 0 ] NEW_LINE profits . remove ( profits [ 0 ] ) NEW_LINE k -= 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT k = 3 NEW_LINE prices = [ 1 , 12 , 10 , 7 , 10 , 13 , 11 , 10 , 7 , 6 , 9 ] NEW_LINE n = len ( prices ) NEW_LINE print ( " Maximum ▁ profit ▁ is " , maxProfit ( n , k , prices ) ) NEW_LINE DEDENT