#3788

Maximum Score of a Split

medium · 51.5% accepted · 70 likes · top 41%

array · prefix sum

Description

You are given an integer array nums of length n.

Choose an index i such that 0 <= i < n - 1.

For a chosen split index i:

- Let prefixSum(i) be the sum of nums[0] + nums[1] + ... + nums[i].

- Let suffixMin(i) be the minimum value among nums[i + 1], nums[i + 2], ..., nums[n - 1].

The score of a split at index i is defined as:

score(i) = prefixSum(i) - suffixMin(i)

Return an integer denoting the maximum score over all valid split indices.

Solution