Getting everything ready for you…

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

0s

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

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

  1. With unlimited transactions, any rising stretch can be split into one-day trades with the same total profit.
  2. 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