Let dp[i][j][x == 0/1] be the maximum strength to select j disjoint subarrays from the original array’s suffix (nums[i..(n - 1)]), x denotes whether we select the element or not.
提示 2
Initially dp[n][0][0] == 0.
提示 3
We have
dp[i][j][1] = nums[i] * get(j) + max(dp[i + 1][j - 1][0], dp[i + 1][j][1]) where get(j) = j if j is odd, otherwise -j.
提示 4
We can select nums[i] as a separate subarray or select at least nums[i] and nums[i + 1] as the first subarray.
dp[i][j][0] = max(dp[i + 1][j][0], dp[i][j][1]).
