Description:
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).
Solution:
Time Complexity : O(n^2)
Space Complexity: O(n)
var maxProfit = function(k, prices) {
if(!prices.length) return 0;
// Create dp arrays
const even = Array(prices.length).fill(0)
const odd = Array(prices.length).fill(0)
for(let i = 1; i < k+1; i++) {
let prevMax = -Infinity
// Switch arrays to proper values when we are on an odd or even number
const current = i % 2 === 0 ? even : odd;
const prev = i % 2 === 0 ? odd : even;
// Fill dp arrays with max profit on each day when making i amount of transactions
for(let j = 1; j < prices.length; j++) {
prevMax = Math.max(prevMax, prev[j-1] - prices[j-1])
// current[j-1] means we will do nothing on the j day and take the max profit from the previous day
// prices[j] + prevMax is the profit from gained on this day (prices[j]) and the max profit we could make from a previous transaction (prevMax)
current[j] = Math.max(current[j-1], prices[j]+prevMax)
}
}
// Current and prev change based on i. This chooses the correct curent array
return k % 2 === 0 ? even[even.length-1] : odd[odd.length-1]
};
Top comments (0)