maximum-profit.md

Maximum Profit

In the stock market, a person buys a stock and sells it on some future date. Given the stock prices of N days in an array A[ ] and a positive integer K, find out the maximum profit a person can make in at-most K transactions. A transaction is equivalent to (buying + selling) of a stock and new transaction can start only when the previous transaction has been completed.

DP Table (Hint)

Sample Input

2
6
10 22 5 75 65 80

Sample Output

87

Solution

class Solution {
  public:
    int maxProfit(int K, int N, int A[]) {

        // DP of Transaction Count vs Price
        vector<vector<int>> TP(K+1, vector<int>(N+1, 0));

        for(int t = 1; t <= K; ++t) {
            for(int p = 1; p <= N; ++p) {
                TP[t][p] = TP[t][p - 1];
                for(int i = 0; i < p; ++i) {
                    TP[t][p] = max(TP[t][p], TP[t-1][i] + A[p-1] - A[i]);
                }
            }
        }
        return TP.back().back();
    }
};

Accepted