thảo luận Leetcode mỗi ngày

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n=prices.length;
        int[][] F=new int[n+1][k+1];
        int res=0;
        for(int i=0;i<=n;i++){
            for(int j=0;j<=k;j++){
                F[i][j]=Integer.MIN_VALUE;
                if(j==0) F[i][j]=0;
                else{
                    int curMin=Integer.MAX_VALUE;
                    for(int t=i-1;t-1>=0;t--){
                        curMin=Math.min(curMin, prices[t-1]);
                        // System.out.println(curMin);
                        if(curMin>=0 && curMin<=prices[i-1]) F[i][j]=Math.max(F[t-1][j-1]+prices[i-1]-curMin, F[i][j]);
                    }
                }
                // System.out.println(i+" "+j+" "+F[i][j]);
                res=Math.max(res, F[i][j]);
            }
        }
        return res;
    }
}

defmodule Solution do
  @default_min -1001

  def max_profit(k, prices) do
    n = Enum.count(prices)

    cond do
      k == 0 -> 0

      k >= n - 1 ->
        prices
        |> Stream.chunk_every(2, 1, :discard)
        |> Stream.map(fn [a, b] -> max(0, b - a) end)
        |> Enum.sum()

      true ->
        prices =
          prices
          |> Stream.with_index()
          |> Stream.map(fn {v, i} -> {i, v} end)
          |> Map.new()

        for trans <- 1..k, reduce: %{} do
          dp ->
            for day <- 1..(n - 1), reduce: {@default_min, dp} do
              {prev_max_profit, dp} ->
                max_profit =
                  max(prev_max_profit, get(dp, {trans - 1, day - 1}) - get(prices, day - 1))

                {max_profit,
                 Map.put(
                   dp,
                   {trans, day},
                   max(get(dp, {trans, day - 1}), get(prices, day) + max_profit)
                 )}
            end
            |> elem(1)
        end
        |> get({k, n - 1})
    end
  end

  defp get(map, key), do: Map.get(map, key, 0)
end

    int maxProfit(int k, vector<int>& prices) {
        auto f = [&](auto& f, int j, bool buying, int i) -> int {
            if (j == 0 || i >= prices.size()) return 0;
            const int buyOrSell = (buying ? -prices[i] : prices[i]) + f(j - !buying, !buying, i + 1);
            const int ignore = f(j, buying, i + 1);
            return max(buyOrSell, ignore);
        };
        return memoize(f, k, true, 0);
    }

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n, p = len(prices) - 1, -1
        profits, vp = [], []
        while p < n:
            v = p + 1
            while v < n and prices[v] >= prices[v + 1]: v += 1
            p = v
            while p < n and prices[p] <= prices[p + 1]: p += 1
         
            while vp and prices[v] < prices[vp[-1][0]]:
                pv, pp = vp.pop()
                profits.append(prices[pp] - prices[pv])
            while vp and prices[p] >= prices[vp[-1][1]]:
                pv, pp = vp.pop()
                profits.append(prices[pp] - prices[v])
                v = pv
            vp.append((v, p))
        else:
            profits.extend(prices[p] - prices[v] for v, p in vp)
         
        return sum(nlargest(k, profits))

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size(), res = 0;
        if (n < 2) return 0;
        vector<int> T(n), tmp(n);
      
        for (int t = 1; t <= k; ++t) {
            int tt = tmp[1] = t == 1 ? max(prices[1] - prices[0], 0) : 0;
            for (int i = 2; i < n; ++i) {
                tt = max(tt + prices[i] - prices[i-1], T[i-2] + prices[i] - prices[i-1]);
                tmp[i] = max(tmp[i-1], tt);
            }
            T.swap(tmp);
            res = max(res, T.back());
        }
      
        return res;
    }
};