410. Split Array Largest Sum

Given an array which consists of non-negative integers and an integerm, you can split the array intomnon-empty continuous subarrays. Write an algorithm to minimize the largest sum among thesemsubarrays.

Note: Ifnis the length of array, assume the following constraints are satisfied:

• 1 ≤ n ≤ 1000

• 1 ≤ m ≤ min(50, n)

Examples:

Input:

nums = [7,2,5,10,8]

m = 2

Output:18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

Thoughts:

1. Binary search to query the minimum value of partition until converge. As per each partition size, there is a number of partition calculated. (Original post)

2. DP: dp[i][j] = min{max{dp[k][j-1], subsum(k + 1, i)}}, 0 <= k < i (Original post)

3. DP: 1D state array with appropriate initialization direction: r from 2 to m, k is shared for the same r (cuts), decreasing from n-1 to r, i (subarray boundary) is decreasing frm n to r

Code: Binary search through ranges of values. T: O(nlogn)

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int max_val = 0; long sum = 0;
        for (int num : nums){
            max_val = max(max_val, num);
            sum += num;
        }
        // if (m == 1) return (int)sum;
        long l = max_val , r = sum;
        while(l <= r){
            int mid = l + (r - l >> 1);
            if(valid_partition(mid, nums, m)){
                r = mid - 1;
            }
            else l = mid + 1;
        }

        return (int)l;
    }

    bool valid_partition(int target, vector<int>& nums, int m){
        int count = 1; long total = 0;
        for (int num: nums){
            total += num;
            if (total > target){
                count ++;
                total = num;
                if (count > m) return false;
            }
        }

        return true;
    }
};

Code: DP T: O(n^2m)

class Solution(object):
    def splitArray(self, nums, m):
        """
        :type nums: List[int]
        :type m: int
        :rtype: int
        """
        n = len(nums)
        if not n: 
            return 0
        pre_sum = [0] * (n + 1)
        for i in range(n):
            pre_sum[i + 1] = pre_sum[i] + nums[i]

        sub_sum = lambda i, j: pre_sum[j + 1] - pre_sum[i]
        sub_cand = lambda k, j, i: max(dp[k][j], sub_sum(k + 1, i))

        # dp = [[0] * m for _ in range(n)]
        dp = [[0 for _ in range(m + 1)] for _ in range(n)]

        for i in range(n):
            dp[i][1] = pre_sum[i + 1]
            k = 0 
            for j in range(2, m + 1): # assume j <= i + 1
                # while k + 1 < i and max(dp[k][j - 1], sub_sum(k+1, i)) > max(dp[k + 1][j - 1], sub_sum(k + 2, i)):
                min_val = pre_sum[-1]
                for k in range(i + 1):
                    min_val = min(min_val, sub_cand(k, j - 1, i))
                dp[i][j] = min_val

        return dp[n - 1][m]

Code: DP T: O(nm), S: O(n)

class Solution(object):
    def splitArray(self, nums, m):
        '''
        O(n) space
        '''
        n = len(nums)
        sums = [0]
        for v in nums:
            sums+= [sums[-1]+v]
        dp = list(sums)

        dp_cal = lambda j: max(dp[j], sums[i]-sums[j])

        for r in range(2, m + 1):
            k = n - 1
            for i in range(n, r - 1, -1):
                while k >= r and dp_cal(k-1) <= dp_cal(k):
                    k -= 1
                dp[i] = dp_cal(k)

        return dp[n]

# """
# This is Master's API interface.
# You should not implement it, or speculate about its implementation
# """
#class Master(object):
#    def guess(self, word):
#        """
#        :type word: str
#        :rtype int
#        """

class Solution(object):
    def findSecretWord(self, wordlist, master):
        """
        :type wordlist: List[Str]
        :type master: Master
        :rtype: None
        """
        match = lambda w1, w2: sum(i == j for i, j in zip(w1, w2))

        n = 0 
        while n < 6:
            count = collections.Counter(w1 for w1, w2 in itertools.permutations(wordlist, 2) if match(w1, w2) == 0)
            guess = min(wordlist, key = lambda w: count[w])
            n = master.guess(guess)
            wordlist = [w for w in wordlist if match(w, guess) == n]