Compute maximum later-earlier difference

Q: Compute maximum later-earlier difference

This question evaluates array-processing and algorithmic optimization skills, testing reasoning about element relationships in sequences; it falls under the Coding & Algorithms domain and emphasizes practical application of linear-time algorithm design rather than purely conceptual proofs.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

You are given an integer array output (length n ≥ 1).

Define the gain of choosing indices i < j as output[j] - output[i].

Return the maximum gain over all valid pairs (i, j). If no pair yields a positive gain, return 0.

Input

output : vector<int>

Output

An integer: the maximum possible output[j] - output[i] for i < j , or 0 if all differences are non-positive.

Examples

output = [7, 1, 5, 3, 6, 4] → 5 (buy at 1 , sell at 6 )
output = [5, 4, 3, 2, 1] → 0

Constraints (typical)

1 ≤ n ≤ 2e5
-1e9 ≤ output[i] ≤ 1e9

Implement int root_node(vector<int> output) efficiently (time better than O(n²)).

Compute maximum later-earlier difference

Quick Overview

Input

Output

Examples

Constraints (typical)

Comments (0)