maximum-score-of-a-split

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an integer array <code>nums</code> of length <code>n</code>.

Choose an index <code>i</code> such that <code>0 &lt;= i &lt; n - 1</code>.

For a chosen split index <code>i</code>:

<ul>
	<li>Let <code>prefixSum(i)</code> be the sum of <code>nums[0] + nums[1] + ... + nums[i]</code>.</li>
	<li>Let <code>suffixMin(i)</code> be the minimum value among <code>nums[i + 1], nums[i + 2], ..., nums[n - 1]</code>.</li>
</ul>

The score of a split at index <code>i</code> is defined as:

<code>score(i) = prefixSum(i) - suffixMin(i)</code>

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

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [10,-1,3,-4,-5]

Output: 17

Explanation:

The optimal split is at <code>i = 2</code>, <code>score(2) = prefixSum(2) - suffixMin(2) = (10 + (-1) + 3) - (-5) = 17</code>.
</div>

Example 2:

<div class="example-block">
Input: nums = [-7,-5,3]

Output: -2

Explanation:

The optimal split is at <code>i = 0</code>, <code>score(0) = prefixSum(0) - suffixMin(0) = (-7) - (-5) = -2</code>.
</div>

Example 3:

<div class="example-block">
Input: nums = [1,1]

Output: 0

Explanation:

The only valid split is at <code>i = 0</code>, <code>score(0) = prefixSum(0) - suffixMin(0) = 1 - 1 = 0</code>.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= nums.length &lt;= 105</code></li>
	<li><code>-109​​​​​​​ &lt;= nums[i] &lt;= 109</code></li>
</ul>