Maximum Strength of K Disjoint Subarrays
Source: leetcode
Difficulty: Hard
Tags: array, dynamic-programming, prefix-sum

You are given an array of integers `nums` with length `n`, and a positive **odd** integer `k`.


Select exactly **`k`** disjoint subarrays **`sub1, sub2, ..., subk`** from `nums` such that the last element of `subi` appears before the first element of `sub{i+1}` for all `1 <= i <= k-1`. The goal is to maximize their combined strength.


The strength of the selected subarrays is defined as:


`strength = k * sum(sub1)- (k - 1) * sum(sub2) + (k - 2) * sum(sub3) - ... - 2 * sum(sub{k-1}) + sum(subk)`


where **`sum(subi)`** is the sum of the elements in the `i`\-th subarray.


Return the **maximum** possible strength that can be obtained from selecting exactly **`k`** disjoint subarrays from `nums`.


**Note** that the chosen subarrays **don't** need to cover the entire array.


 


**Example 1:**


**Input:** nums \= \[1,2,3,\-1,2], k \= 3


**Output:** 22


**Explanation:**


The best possible way to select 3 subarrays is: nums\[0\..2], nums\[3\..3], and nums\[4\..4]. The strength is calculated as follows:


`strength = 3 * (1 + 2 + 3) - 2 * (-1) + 2 = 22`


 


**Example 2:**


**Input:** nums \= \[12,\-2,\-2,\-2,\-2], k \= 5


**Output:** 64


**Explanation:**


The only possible way to select 5 disjoint subarrays is: nums\[0\..0], nums\[1\..1], nums\[2\..2], nums\[3\..3], and nums\[4\..4]. The strength is calculated as follows:


`strength = 5 * 12 - 4 * (-2) + 3 * (-2) - 2 * (-2) + (-2) = 64`


**Example 3:**


**Input:** nums \= \[\-1,\-2,\-3], k \= 1


**Output:** \-1


**Explanation:**


The best possible way to select 1 subarray is: nums\[0\..0]. The strength is \-1\.


 


**Constraints:**


- `1 <= n <= 104`
- `-109 <= nums[i] <= 109`
- `1 <= k <= n`
- `1 <= n * k <= 106`
- `k` is odd.




C++ solution:
class Solution {
public:
    long long maximumStrength(vector<int>& nums, int k) {
        std::vector<int> work = nums;
        work.insert(work.begin(), 0);
        const int n = static_cast<int>(nums.size());
        std::vector<long> dp(k + 1, static_cast<long>(-1e15));
        dp[0] = 0;
        long result = -1e18;
        for (int i = n; i >= 1; --i)
        {
            for (int j = std::min(k, n - i + 1); j >= 1; --j)
            {
                long sign = 2 * (j & 1) - 1;
                dp[j] = std::max({dp[j], dp[j - 1], dp[j - 1]})
                    + sign * work[i] * j;
                if (j == k)
                    result = std::max(result, dp[j]);
            }
        }
        return result;
    }
};

Go solution:
func maximumStrength(nums []int, k int) int64 {
    n := len(nums)
	dp := make([]int64, n + 1)

	for j := 0; j < k; j++ {
		mul := int64(k - j)
		if j % 2 == 1 {
			mul = -mul
		}

		tmp := make([]int64, n + 1)
		tmp[0] = math.MinInt64 / 2

		for i := 1; i <= n; i++ {
			tmp[i] = max(tmp[i - 1], dp[i - 1]) + int64(nums[i - 1]) * mul
		}

		copy(dp, tmp)

		for i := 1; i <= n; i++ {
			dp[i] = max(dp[i], dp[i - 1])
		}
	}

	return dp[n]
}

func max(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

Java solution:
class Solution {
    public long maximumStrength(int[] nums, int k) {
        long[][] dp = new long[k + 1][nums.length + 1];
        for (int i = 1; i <= k; i++) {
            long maxSum = Long.MIN_VALUE /2;
            long curr = Long.MIN_VALUE/2;
            long multiplier = (i % 2 == 1) ? (k + 1 - i) : (i - 1 - k);
            for (int j = i - 1; j < nums.length; j++) {
                curr = Math.max(curr + nums[j] * multiplier, dp[i - 1][j] + nums[j] * multiplier);
                maxSum = Math.max(maxSum, curr);
                dp[i][j + 1] = maxSum;
            }
        }
        return dp[k][nums.length];
    }
}

JavaScript solution:
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maximumStrength = function(nums, k) {
    const n = nums.length;
    const small = -Infinity; // initial value as not visited
    const dp = new Array(n).fill(0).map(el=>new Array(2).fill(0).map(el=>new Array(k+1).fill(small)))
    function helper(i, g, x) {
        if(g === 0) {
            return 0;
        }
        if(i === n) {
            // if current is selected and this is the last 1 group
            if(g===1 && x===1) {
                return 0;
            }
            return -Math.pow(10, 15);
        }
        if(dp[i][x][g] != small) {
            // if previous visited, return the cached value.
            return dp[i][x][g];
        }
        const bit = g % 2 === 0 ? -1 : 1;

        // case1: select i element  = (create a new sub) OR (include i into current)
        const res1 = Math.max(helper(i+1, g-1, 0),helper(i+1, g, 1))  + nums[i] * bit * g;
        
        // case2: doesn't select i
        const res2 = (x===0)  ? helper(i+1, g, 0) : small;
        const res = Math.max(res1, res2);
        dp[i][x][g] = res;
        return res;
    }

    return helper(0,k,0);
};

Python solution:
class Solution:
    def maximumStrength(self, nums: List[int], k: int) -> int:
        number = -1_000_000_000_000_000
        dp=[[number]*len(nums) for i in range(k)]
        dp[0][0]=nums[0]*k
        for i in range(1,len(nums)):
            dp[0][i]=max(dp[0][i-1]+nums[i]*k,nums[i]*k)
        for i in range(1,k):
            check=k-i if i%2==0 else i-k
            for j in range(i,len(nums)):
                dp[i][j]=nums[j]*check+max(dp[i-1][j-1],dp[i][j-1])

        ret=-1000000000000000
        for i in range(len(nums)):
            ret=max(ret,dp[k-1][i])

        return ret

Ruby solution:
# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer}
def maximum_strength(nums, k)
  dp = Array.new(k) { Array.new(nums.length, -Float::INFINITY) }
  dp[k - 1][0] = nums[0] * k

  (1...nums.length).each do |i|
    (k - 1).downto(0) do |j|
      dp[j][i] = [dp[j][i - 1], (j + 1 < k ? dp[j + 1][i - 1] : 0)].max + nums[i] * (j + 1) * ((j & 1 == 1) ? -1 : 1)
    end
  end
  dp[0].max
end