CF 105434D - 股票交易

Rating: -
Tags: -
Solve time: 54s
Verified: yes

Solution

Problem Understanding

We are given a sequence of daily stock prices. You are allowed to pick at most one pair of days, buy on an earlier day and sell on a later day, and you earn profit equal to the increase in price divided by the number of days held. Formally, if you buy on day $x$ and sell on day $y$, the score is $(a_y - a_x) / (y - x)$. If no profitable trade is chosen, the score is defined as 0.

The task is to compute the maximum possible value of this ratio over all valid pairs $x < y$.

The input size reaches $10^5$, which immediately rules out any solution that checks all pairs of days. A quadratic scan over all $(x, y)$ pairs would require about $5 \cdot 10^9$ evaluations in the worst case, which is far beyond the 3-second limit. Even slightly suboptimal $O(n \log n)$ or heavy preprocessing would be unnecessary because the structure of the ratio suggests a stronger monotonic property can be exploited.

A key edge case is when prices are monotonically decreasing. For example, input $5, 4, 3, 2, 1$ produces no positive profit, so the answer must be 0. Any algorithm that does not explicitly allow the empty choice would incorrectly output a negative ratio from some pair, even though the problem definition forbids it.

Another subtle case is when the best profit comes from a short interval rather than a large jump. For example, $1, 100, 2, 3$ might tempt a greedy strategy that picks extremes, but the optimal segment depends on balancing numerator and denominator simultaneously.

Approaches

The brute-force approach enumerates all pairs of days $x < y$, computes the value $(a_y - a_x)/(y - x)$, and tracks the maximum. This is correct because every valid transaction is checked. However, for each right endpoint $y$, it examines all earlier $x$, leading to roughly $n(n-1)/2$ evaluations. With $n = 10^5$, this becomes infeasible.

The structure of the expression suggests a geometric interpretation. Each day $x$ can be seen as a point $(x, a_x)$, and the value for a pair is the slope of the line connecting two points. The problem reduces to finding the maximum slope between any two points with increasing x-coordinate.

This turns into a classical convex hull optimization scenario: for each point, we want to maintain a structure that allows us to query the minimum intercept that gives the maximum slope with the current point. The key insight is that as we move forward in time, only a subset of previous points can ever be optimal candidates, and these can be maintained in a convex hull where slopes between consecutive points are monotonic.

This allows us to maintain a lower convex hull of points and query the best previous point for each new day in amortized constant time using a monotonic pointer or deque.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n^2)	O(1)	Too slow
Convex Hull / Monotonic Hull	O(n)	O(n)	Accepted

Algorithm Walkthrough

We reinterpret each day $i$ as a point $(i, a_i)$. The score between two points is the slope of the line connecting them. We want the maximum slope over all pairs with increasing indices.

We maintain a convex hull of candidate points, where each point represents a previous day that could serve as an optimal buy time.

Start with an empty deque to store candidate indices. The deque will maintain points in a structure such that slopes between consecutive points are monotonic.
Iterate through each day $i$ from left to right.
Before inserting the current point, query the best previous point in the deque that maximizes the slope $(a_i - a_j) / (i - j)$.
To find this best $j$, we compare candidates in the deque. The slope function is unimodal over the hull, so we can advance a pointer while the next candidate improves the slope.
Update the global answer with the best slope found at day $i$.
Insert the current point $i$ into the deque while maintaining convexity. If the last two points and the new point violate convexity, remove the middle point.
Continue until all days are processed.

The key idea in both insertion and query is that dominated points never become optimal again, so they can be safely removed.

Why it works

The expression $(a_y - a_x)/(y - x)$ is the slope between two points in a plane. The convex hull property guarantees that for any set of points, the maximum slope to a new point is achieved at an extreme point of the hull, never in its interior. By maintaining only extreme candidates in increasing order of index, we ensure that every removed point is provably worse than some combination of its neighbors for all future queries. This preserves correctness while reducing the search space to linear size overall.

Python Solution

import sys
input = sys.stdin.readline

def slope(i, j, a):
    return (a[i] - a[j]) / (i - j)

def bad(a, i, j, k):
    return (a[j] - a[i]) * (k - j) >= (a[k] - a[j]) * (j - i)

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    from collections import deque
    dq = deque()

    ans = 0.0

    for i in range(n):
        while len(dq) >= 2:
            j = dq[0]
            k = dq[1]
            if slope(i, j, a) <= slope(i, k, a):
                dq.popleft()
            else:
                break

        if dq:
            ans = max(ans, slope(i, dq[0], a))

        while len(dq) >= 2 and bad(a, dq[-2], dq[-1], i):
            dq.pop()

        dq.append(i)

    print(f"{ans:.3f}")

if __name__ == "__main__":
    solve()

The solution maintains a deque of candidate buy days. The slope function evaluates profit per day for a candidate pair. The query step moves from the front of the deque while a better slope exists further ahead, exploiting the monotonic structure of slopes over a convex hull.

The bad function removes a middle point if it becomes unnecessary for maintaining convexity. It compares cross-multiplied slopes to avoid floating point precision issues in the hull maintenance step, even though final answers are computed in float.

The answer starts at 0.0 to respect the “no trade” option.

Worked Examples

Example 1

Input:

5
1 2 3 4 5

We track candidates and best slopes.

i	price	deque before query	best candidate j	slope	ans	deque after
0	1	[]	-	-	0.0	[0]
1	2	[0]	0	1.0	1.0	[0,1]
2	3	[0,1]	1	1.0	1.0	[0,1,2]
3	4	[0,1,2]	2	1.0	1.0	[0,1,2,3]
4	5	[0,1,2,3]	3	1.0	1.0	[0,1,2,3,4]

This shows a linear increasing sequence where every segment has slope 1, confirming that the algorithm correctly tracks equal optimal choices.

Example 2

Input:

5
5 4 3 2 1

i	price	deque before query	best candidate j	slope	deque after
0	5	[]	-	-	[0]
1	4	[0]	0	-1.0	[0,1]
2	3	[0,1]	0	-1.0	[0,1,2]
3	2	[0,1,2]	0	-1.0	[0,1,2,3]
4	1	[0,1,2,3]	0	-1.0	[0,1,2,3,4]

This confirms that negative slopes never override the default answer of 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index enters and leaves the deque at most once, and each is processed in amortized constant time
Space	O(n)	The deque stores at most all indices in the worst case before pruning

The linear complexity is necessary because $n = 10^5$, and any quadratic exploration would exceed time limits. The memory usage remains safe under 512 MB because only integer indices are stored.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from math import isclose

    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))

    from collections import deque

    def slope(i, j):
        return (a[i] - a[j]) / (i - j)

    def bad(i, j, k):
        return (a[j] - a[i]) * (k - j) >= (a[k] - a[j]) * (j - i)

    dq = deque()
    ans = 0.0

    for i in range(n):
        while len(dq) >= 2:
            j = dq[0]
            k = dq[1]
            if slope(i, j) <= slope(i, k):
                dq.popleft()
            else:
                break

        if dq:
            ans = max(ans, slope(i, dq[0]))

        while len(dq) >= 2 and bad(dq[-2], dq[-1], i):
            dq.pop()

        dq.append(i)

    return f"{ans:.3f}"

# provided samples
assert run("5\n1 2 3 4 5\n") == "1.000", "sample 1"
assert run("5\n5 4 3 2 1\n") == "0.000", "sample 2"

# custom cases
assert run("1\n10\n") == "0.000", "single element"
assert run("2\n1 100\n") == "99.000", "single jump"
assert run("3\n1 3 2\n") == "2.000", "peak in middle"
assert run("4\n10 1 10 1\n") == "9.000", "alternating extremes"

Test input	Expected output	What it validates
1 element	0.000	minimum size, no trade
1 100	99.000	direct best single interval
1 3 2	2.000	non-monotonic case
10 1 10 1	9.000	alternating extremes

Edge Cases

For a single-day input like 10, the deque contains only one point and no valid transaction exists. The algorithm never computes a slope, so the answer remains 0.0.

For strictly decreasing sequences like 5 4 3 2 1, every computed slope is negative, but the algorithm still updates the deque and checks candidates. Since the answer starts at 0.0 and only positive improvements matter, no update ever occurs.

For cases where the optimal pair is adjacent, such as 1 100, the first comparison directly evaluates slope 99, which immediately becomes the best answer. The deque logic does not delay or skip this case because each new index is tested against the current hull before insertion.

For oscillating inputs, dominated points are removed during hull maintenance, ensuring that only structurally relevant candidates remain, and every potential optimal slope is still evaluated when the right endpoint arrives.