# Question

Formatted question description: https://leetcode.ca/all/188.html

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: i.e. you may buy at most k times and sell at most k times.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

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.


Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.


Constraints:

• 1 <= k <= 100
• 1 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

# Algorithm

Extend from problem-123.

Define local[i][j] as the maximum profit that can be made at most j transactions on the i-th day and the last transaction sold on the last day, which is the local optimal.

Then we define global[i][j] as the maximum profit that can be performed at most j transactions when the i-th day is reached, which is the global optimal (not neccessarily last transaction sold on the last day). Their recurrence is:

local[i][j] = max(global[i-1][j-1] + max(diff, 0), local[i-1][j] + diff)

global[i][j] = max(local[i][j], global[i-1][j])


The local optimal value is compared to the global optimal one less traded the previous day plus a difference greater than 0, and the local optimal of the previous day plus the difference, whichever is greater, and the global optimal compares the local optimal And the previous day’s global optimal.

# Code

• 

class Solution {
public int maxProfit(int k, int[] prices) {

int n = prices.length;
if (n <= 1) {
return 0;
}

int[][] g = new int[n][k + 1];
int[][] l = new int[n][k + 1];

for (int i = 1; i < prices.length; ++i) {
int diff = prices[i] - prices[i - 1];
for (int j = 1; j <= k; ++j) {
// 最后一天卖出, 因为已经j次交易，j次的买入已经完成 => l[i - 1][j] + diff
l[i][j] = Math.max(g[i - 1][j - 1] + Math.max(diff, 0), l[i - 1][j] + diff);
g[i][j] = Math.max(l[i][j], g[i - 1][j]); // 第j天有没有卖出，两种情况
}
}

return g[n - 1][k];
}
}

class Solution_1D {
public int maxProfit(int k, int[] prices) {

int n = prices.length;
if (n <= 1) {
return 0;
}

//if k >= n/2, then you can make maximum number of transactions.
if (k >= n / 2) {
int maxPro = 0;
for (int i = 1; i < n; i++) {
if (prices[i] > prices[i - 1])
maxPro += prices[i] - prices[i - 1];
}
return maxPro;
}

int[] global = new int[k + 1];
int[] local = new int[k + 1]; // k=0, no transaction, profit=0
for (int i = 0; i < prices.length - 1; i++) {
int diff = prices[i + 1] - prices[i];
for (int j = k; j >= 1; --j) {
local[j] = Math.max(global[j - 1] + Math.max(diff, 0), local[j] + diff);
global[j] = Math.max(global[j], local[j]);
}
}

return global[k];
}
}
}

############

class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if (n <= 1) {
return 0;
}
int[][][] dp = new int[n][k + 1][2];
for (int i = 1; i <= k; ++i) {
dp[0][i][1] = -prices[0];
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= k; ++j) {
dp[i][j][0] = Math.max(dp[i - 1][j][1] + prices[i], dp[i - 1][j][0]);
dp[i][j][1] = Math.max(dp[i - 1][j - 1][0] - prices[i], dp[i - 1][j][1]);
}
}
return dp[n - 1][k][0];
}
}

• // OJ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii
// Time: O(KN^2)
// Space: O(KN)
// NOTE: this will get TLE
class Solution {
public:
int maxProfit(int K, vector<int>& A) {
if (A.empty()) return 0;
int N = A.size();
K = min(K, N / 2);
vector<vector<int>> dp(K + 1, vector<int>(N + 1));
for (int k = 1; k <= K; ++k) {
for (int i = 1; i < N; ++i) {
int maxVal = INT_MIN;
for (int j = 0; j < i; ++j) maxVal = max(maxVal, dp[k - 1][j] - A[j]);
dp[k][i + 1] = max(dp[k][i], A[i] + maxVal);
}
}
return dp[K][N];
}
};

• class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
n = len(prices)
if n < 2:
return 0
# 3-D dp: n days * k completed transactions * 2 ops buy/sell
# my understanding, one transaction, meaning both buy then sell completed
dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n)]
for i in range(1, k + 1):
dp[0][i][1] = -prices[0] # dp[][][ 0/1 ], 1 is buy, 0 is sell
for i in range(1, n):
for j in range(1, k + 1):
dp[i][j][0] = max(dp[i - 1][j][1] + prices[i], dp[i - 1][j][0]) # [1] => sell happening <= that day
dp[i][j][1] = max(dp[i - 1][j - 1][0] - prices[i], dp[i - 1][j][1])
return dp[-1][k][0]

class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
@cache
def dfs(i, j, k):
if i >= len(prices):
return 0
ans = dfs(i + 1, j, k)
if k:
ans = max(ans, prices[i] + dfs(i + 1, j, 0))
elif j:
ans = max(ans, -prices[i] + dfs(i + 1, j - 1, 1))
return ans

return dfs(0, k, 0)

##############

import heapq
import random

class Solution(object):
def findKthLargest(self, nums, k):
"""
:type A: List[int]
:type k: int
:rtype: int
"""

def quickselect(start, end, nums, k):
if start == end:
return nums[start]

mid = partition(start, end, nums)

if mid == k:
return nums[mid]
elif k > mid:
return quickselect(mid + 1, end, nums, k)
else:
return quickselect(start, mid - 1, nums, k)

def partition(start, end, nums):
p = random.randrange(start, end + 1)
pv = nums[p]
nums[end], nums[p] = nums[p], nums[end]
mid = start
for i in range(start, end):
if nums[i] >= pv:
nums[i], nums[mid] = nums[mid], nums[i]
mid += 1
nums[mid], nums[end] = nums[end], nums[mid]
return mid

return quickselect(0, len(nums) - 1, nums, k - 1)

def maxProfit(self, k, prices):
"""
:type k: int
:type prices: List[int]
:rtype: int
"""
if not prices:
return 0
stack = []
heap = []
v = p = 0
n = len(prices)
ans = 0
while p < n:
v = p
while v < n - 1 and prices[v] >= prices[v + 1]:
v += 1
p = v + 1
while p < n and prices[p] > prices[p - 1]:
p += 1
while stack and prices[stack[-1][0]] > prices[v]:
_v, _p = stack.pop()
heap.append(prices[_p - 1] - prices[_v])
while stack and prices[stack[-1][1] - 1] < prices[p - 1]:
heap.append(prices[stack[-1][1] - 1] - prices[v])
v, _ = stack.pop()
stack.append((v, p))

heap += [prices[p - 1] - prices[v] for v, p in stack]
if len(heap) < k:
return sum(heap)
self.findKthLargest(heap, k)
return sum(heap[:k])


• func maxProfit(k int, prices []int) int {
n := len(prices)
if n < 2 {
return 0
}
dp := make([][][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([][]int, k+1)
for j := 0; j <= k; j++ {
dp[i][j] = make([]int, 2)
}
}
for i := 1; i <= k; i++ {
dp[0][i][1] = -prices[0]
}
for i := 1; i < n; i++ {
for j := 1; j <= k; j++ {
dp[i][j][0] = max(dp[i-1][j][1]+prices[i], dp[i-1][j][0])
dp[i][j][1] = max(dp[i-1][j-1][0]-prices[i], dp[i-1][j][1])
}
}
return dp[n-1][k][0]
}

func max(a, b int) int {
if a > b {
return a
}
return b
}

• using System;
using System.Collections.Generic;
using System.Linq;

public class Comparer : IComparer<LinkedListNode<Tuple<int, int>>>
{
{
var result = left.Value.Item1.CompareTo(right.Value.Item1);
if (result == 0 && left != right)
{
return left.Value.Item2.CompareTo(right.Value.Item2);
}
return result;
}
}

public class Solution {

private int lable = 0;
private Tuple<int, int> CreateNodeValue(int value)
{
return Tuple.Create(value, lable++);
}

public int MaxProfitStupid(int k, int[] prices)
{
var f = new int[prices.Length + 1, k + 1];
for (var i = 2; i <= prices.Length; ++i)
{
for (var kk = 1; kk <= k; ++kk)
{
for (var j = 0; j + 1 < i; ++j)
{
f[i, kk] = Math.Max(f[i, kk], Math.Max(Math.Max(f[i, kk - 1], f[i - 1, kk]), f[j, kk - 1] + prices[i - 1] - prices[j]));
}
}
}
return f[prices.Length, k];
}

public int MaxProfit(int k, int[] prices) {
var result = 0;
var i = 0;
var profitCount = 0;
var tempList = new List<Tuple<int, bool>>();
while (i + 1 < prices.Length)
{
var highIndex = i;
while (i + 1 < prices.Length && prices[i] >= prices[i + 1])
{
++i;
}
var lowIndex = i;
while (i + 1 < prices.Length && prices[i] <= prices[i + 1])
{
++i;
}
var highIndex2 = i;

if (highIndex != lowIndex)
{
}
if (lowIndex != highIndex2)
{
result += prices[highIndex2] - prices[lowIndex];
++profitCount;
}
}

// Trim gaps
if (tempList.Any() && tempList.First().Item2 == false)
{
tempList.RemoveAt(0);
}
if (tempList.Any() && tempList.Last().Item2 == false)
{
tempList.RemoveAt(tempList.Count - 1);
}

foreach (var temp in tempList)
{
}
//Console.WriteLine("profitCount: {0}. tempList size: {1}. Heap size: {2}.", profitCount, tempList.Count, heap.Sum(item =>item.Value.Count));

for (var j = 0; j < profitCount - k; ++j)
{
var node = heap.Min;
result -= node.Value.Item1;
//Console.WriteLine(node.Value);
var previous = node.Previous;
var next = node.Next;
var newValue = (previous == null ? 0 : previous.Value.Item1) + (next == null ? 0 : next.Value.Item1) - node.Value.Item1;
if (previous != null)
{
heap.Remove(previous);
list.Remove(previous);
}
if (next != null)
{
heap.Remove(next);
list.Remove(next);
}
if (previous != null && next != null)
{