Practice › Dynamic Programming
Stock Trading with Cooldown
Medium · Dynamic Programming · Asked at Amazon, Google, Microsoft, Goldman Sachs
You may buy and sell many times (holding at most one share), but after selling you must wait one day before buying again. Print the maximum profit.
Input
First line: n. Second line: n space-separated integers.
Output
The maximum profit.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ price ≤ 1000
Three states per day: holding a share, just sold (cooldown next day), and free to buy. Write each state from the previous day's states.
Example 1
Input
5 1 2 3 0 2
Output
3
Example 2
Input
1 1
Output
0
Hints
- Describe each day by a state: holding a share, just sold today, or resting (free to buy).
- hold = max(hold, rest − price); sold = hold + price; rest = max(rest, sold) — all computed from the previous day's values.
Approach
A state machine DP. Buying is only allowed from rest, which enforces the cooldown: after selling you are in sold, and only the next day can you move to rest. Update all three states simultaneously from yesterday's values. The answer is max(sold, rest) — ending while holding a share is never optimal.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
long long hold = LLONG_MIN / 2, sold = 0, rest = 0;
for (int i = 0; i < n; i++) {
long long p;
cin >> p;
long long h = max(hold, rest - p), s = hold + p, r = max(rest, sold);
hold = h, sold = s, rest = r;
}
cout << max(sold, rest) << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
hold, sold, rest = float("-inf"), 0, 0
for p in data[1 : 1 + data[0]]:
hold, sold, rest = max(hold, rest - p), hold + p, max(rest, sold)
print(max(sold, rest))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long hold = Long.MIN_VALUE / 2, sold = 0, rest = 0;
for (int i = 0; i < n; i++) {
long p = sc.nextLong();
long h = Math.max(hold, rest - p), s = hold + p, r = Math.max(rest, sold);
hold = h;
sold = s;
rest = r;
}
System.out.println(Math.max(sold, rest));
}
}Solve Stock Trading with Cooldown online · All practice problems