Accepted 8ms C++


  • 6
    M
    int maxProfit(int k, vector<int>& prices) {
        int n = (int)prices.size();
        if (n <= 1) return 0;
        int fm = 0, km = 0;
        for (int j = 1; j < n; j++) {
            int f = prices[j]-prices[j-1];
            if (f>0) {
                fm += f;
                km++;
            }
        }
        if (k >= km) {
            return fm;
        } else {
            int f[n], prev;
            fill_n(f, n, 0);
            for (int i = 1; i <= k; i++) {
                int S = INT_MIN;
                prev = f[0];
                for (int j = 1; j < n; j++) {
                    S = std::max(S, prev-prices[j-1]);
                    prev = f[j];
                    f[j] = std::max(f[j-1], S+prices[j]);
                }
            }
            return f[n-1];
        }

  • 0
    S

    can you explain what is f[i] array? I don't understand the loop of i [1..k] and the inner loop j [1..n). Thanks!


  • 0
    M

    First, it is DP solution. f[j] array save the max profit up to prices[j] with at most i transactions. So the loop of i =1:k is for number of transactions, and inner loop of j = 1 : n is for compute the profit. Hope this helps.


  • 0
    S

    For loop i = 1:K, for example, when i =1, means # of transactions is 1, why the inter loop has "n" transactions? What is f[j] for later loop?


  • 0
    M

    To make it simple, let us do DP with 2D table. f[i][j], So it represents max profit can be made with at most i transactions up to prices[j]. the inner loop "n" means you have n prices. Since f[i][j] computation only depends on f[i-1][j-1] and f[i][j-1], we simplify the memory footprint by use 1D table, f[j]. In the inner loop, prev means f[i-1][j-1], f[j-1] means f[i][j-1], f[j] means f[i][j]. If you substitute these and you will get a clear picture. Surely, in the end, it really means f[k][n-1]. Let me know if you have any confusion.


  • 0
    S

    Thanks, I got it. So one transaction has one buy and one sell. S here is "balance" at price j -1 up to i th transaction.


  • 0
    M

    To be precise, S is the balance before sell, f[j] the balance after sell.


  • 0

    can we sort an array f[] which save f ,then select fisrt kth elements to solve this problem.


  • 0
    M

    Would you please be more specific on this? I do not quite understand your idea.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.