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

Easy · Arrays · Asked at Amazon, Microsoft, Google, Goldman Sachs, Flipkart

price[i] is the stock price on day i. Buy on one day and sell on a later day. Print the maximum profit, or 0 if no profit is possible.

Input

First line: n. Second line: n space-separated integers.

Output

The maximum profit.

Constraints

Example 1

Input

6
7 1 5 3 6 4

Output

5

Example 2

Input

5
7 6 4 3 1

Output

0

Hints

  1. If you sell on day i, the best buying day is the cheapest day before it.
  2. Track the minimum price seen so far and the best profit price[i] − minimum.

Approach

Scan left to right, keeping the lowest price so far. On each day, selling today earns price − lowest; keep the largest such profit. The profit never goes below 0 because the minimum includes today's price.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int lowest = INT_MAX, best = 0, p;
    for (int i = 0; i < n; i++) {
        cin >> p;
        lowest = min(lowest, p);
        best = max(best, p - lowest);
    }
    cout << best << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
lowest, best = float("inf"), 0
for p in data[1 : data[0] + 1]:
    lowest = min(lowest, p)
    best = max(best, p - lowest)
print(best)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), lowest = Integer.MAX_VALUE, best = 0;
        for (int i = 0; i < n; i++) {
            int p = sc.nextInt();
            lowest = Math.min(lowest, p);
            best = Math.max(best, p - lowest);
        }
        System.out.println(best);
    }
}

Solve Best Time to Buy and Sell Stock online · All practice problems