← 返回 citadel 的题目列表Refactor and Optimize a Slow Function
类型：online_judge
Problem: Refactor and Optimize a Slow Function
Given an integer array output (length n, n >= 1), you need to refactor and speed up a “correct but slow” implementation.
The final return value can be equivalently defined as:
Scan the array from left to right while maintaining the minimum value seen so far min_prefix.
For each element a[i], compute a[i] - min_prefix.
Return the maximum of these differences (ignoring negatives, equivalently compare with 0).
Formally:
ans = max(0, max_{0<=j<i<n}(output[i] - output[j]))
Implement an O(n) time and O(1) extra space solution.
Input (stdin)
Line 1: integer n
Line 2: n integers representing output
Output (stdout)
Print an integer ans
Constraints
1 <= n <= 2*10^5
-10^9 <= output[i] <= 10^9
Example
Input: n=5, output=[7,1,5,3,6]
Output: 5 (buy at 1, sell at 6)
Example
Input
5
7 1 5 3 6
Output
5