Practice › Arrays
Best Time to Buy and Sell Stock II
Medium · Arrays · Asked at Amazon, Microsoft, Goldman Sachs, Flipkart
a[i] is the price of a stock on day i. You may buy and sell as many times as you like, but you can hold at most one share at a time (sell 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 ≤ a[i] ≤ 10^4
Every upward step a[i] > a[i-1] can be captured — add up all positive day-to-day differences.
Example 1
Input
6 7 1 5 3 6 4
Output
7
Example 2
Input
5 7 6 4 3 1
Output
0
Hints
- With unlimited transactions, any rising stretch can be split into one-day trades with the same total profit.
- So add every positive difference a[i] − a[i−1].
Approach
A trade from day l to day r earns a[r] − a[l], which equals the sum of the daily changes in between. Taking every positive daily change (and skipping negative ones) is therefore at least as good as any set of trades — and it is achievable by buying before each rise and selling after it.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
long long profit = 0;
for (int i = 1; i < n; i++) profit += max(0LL, a[i] - a[i - 1]);
cout << profit << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
a = data[1:]
print(sum(max(0, a[i] - a[i - 1]) for i in range(1, len(a))))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 prev = sc.nextLong(), profit = 0;
for (int i = 1; i < n; i++) {
long x = sc.nextLong();
profit += Math.max(0, x - prev);
prev = x;
}
System.out.println(profit);
}
}Solve Best Time to Buy and Sell Stock II online · All practice problems