Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Describe each day by a state: holding a share, just sold today, or resting (free to buy).
  2. 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