You are given an integer array prices
where prices[i]
is the price of a given stock on the ith
day, and an integer k
.
Find the maximum profit you can achieve. You may complete at most k
transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example:
Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Approach:
C++
#include <bits/stdc++.h>using namespace std;int maxProfit(int k, vector<int> &prices){if (prices.empty())return 0;int n = prices.size();vector<vector<int>> dp(k + 1, vector<int>(n, 0));for (int i = 1; i <= k; i++){int maximumValue = INT_MIN;for (int d = 1; d < n; d++){maximumValue = max(maximumValue,dp[i - 1][d - 1] - prices[d - 1]);dp[i][d] = max(dp[i][d - 1],maximumValue + prices[d]);}}return dp[k].back();}int main(){int k = 2;vector<int> prices = {2, 4, 1};cout << maxProfit(k, prices);return 0;}
No comments:
Post a Comment