Split-and-Keep Stones for Maximum Score
A row of stone values is repeatedly split into a left and right part. The smaller-sum part is kept and added to your score, and you continue on that kept part. Maximize your total score.
Problem
Given an integer array stoneValue, repeatedly: divide the current row into two non-empty contiguous halves. If the two halves have different sums, the smaller sum is added to your score and you keep that smaller half; if equal, you choose which half to keep and add its sum. The game ends when only one stone remains. Return the maximum total score.
Input
An integer array stoneValue.
Output
An integer: the maximum achievable total score.
Constraints
- 1 <= stoneValue.length <= 500
- 1 <= stoneValue[i] <= 10^6
- A single stone yields no further score.
Examples
Example 1
Input
stoneValue = [6,2,3,4,5,5]
Output
18
Optimal sequence of splits accumulates 18 over the rounds.
Example 2
Input
stoneValue = [7,7,7,7,7,7,7]
Output
28
Equal-sum splits let you keep the favorable half repeatedly.