Funcia
Lv.1arraydpmath

Best Pair of Viewpoints

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Viewpoints stand in a row; viewpoint i (0-based) has score scores[i]. Visiting two viewpoints i < j is worth scores[i]+scores[j]−(j−i)\text{scores}[i] + \text{scores}[j] - (j - i). Return the maximum possible value.

Examples

scoresresult
[8, 1, 5, 2, 6]11
[1, 2]2
[1000000000, 1, 1000000000]1999999998

Example 1 — i = 0, j = 2 gives 8+5−2=118 + 5 - 2 = 11. The result can exceed the 32-bit range.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(scores: int[]) → long

Constraints

  • 2≤2 \le scores.length ≤200,000\le 200{,}000
  • 1≤1 \le scores[i] ≤109\le 10^9
  • The answer may not fit in 32 bits; use a 64-bit integer (long).

Expected complexity

Time
O(N)
Space
O(1)

Examples

scoresExpected
[8,1,5,2,6]11
[1,2]2
[1000000000,1,1000000000]1999999998

Hint

Hint

Split the value into (scores[i]+i)+(scores[j]−j)(\text{scores}[i] + i) + (\text{scores}[j] - j). Sweep j from left to right while keeping the best scores[i] + i seen so far. Checking every pair is O(N2)O(N^2) and exceeds the time limit; the sweep is O(N)O(N).

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251038 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.