CodingGyan

Best Time to Buy and Sell Stock

easy Logic and Interview Sets

Problem

Read the price of a stock for each day. You may buy on one day and sell on a LATER day (one trade only). Print the largest possible profit. If no profit is possible print 0.

Constraints

  • 1 <= n <= 10^5

Examples

Input

6
7 1 5 3 6 4

Output

5

Solutions

Best approachTime O(n)Space O(1)

For each day as the selling day, the best buying day is the cheapest day before it. So we keep the minimum while we scan once.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process an array.
 * Input   : n, then n integers.
 * Output  : The best profit.
 * Approach: Track the minimum so far.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int solve(int[] a) {
        // Step 1: Remember the lowest price seen so far. It is the best day to buy.
        int lowest = a[0];
        int bestProfit = 0;

        for (int i = 1; i < a.length; i++) {
            // Step 2: If we sell today, the profit is today's price minus the lowest earlier price.
            bestProfit = Math.max(bestProfit, a[i] - lowest);

            // Step 3: Update the lowest price.
            lowest = Math.min(lowest, a[i]);
        }
        return bestProfit;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(solve(a));
    }
}
Hints (1)
  1. What do you need to remember about the earlier days?

Try these next