Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation

  • Buying and selling stocks

    Given n integers that represent the stock prices of your favorite company, you’d like to decide what would be the best time to buy and sell the stock. You would like to buy the stock only once and sell it only once. So, you’d like to maximize the profit (buy low and sell high).
    Determine the maximum possible profit you can make on your favorite company, and if there is no way to do so, you should print 0 (meaning you won’t buy or sell that stock).

    Input

    The first line of the input contains a single integer n (1 ≤ n ≤ ).
    The next line contains space-separated integers representing the prices of the stock (0 ≤ ≤ 1000).

    Output

    The program should print the maximum possible profit you can make on buying and selling your favorite stock.

    Examples

    Input
    Output
    5 4 2 6 8 1
    6
    4 8 6 4 3
    0

    Explanation

    1. We buy when the stock value is 2 and we sell it when it’s 8
    1. We won’t be able to make any profit as the stock value constantly declines
     
    Hint
    At each point, you can keep a state of the current “best” possible answer and another value for the cheapest the stock has ever been.
     

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue