Skip to content

LeetCode: 410-Split Array Largest Sum 解題紀錄

Last Updated on 2022-03-31 by Clay

題目

Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.

Write an algorithm to minimize the largest sum among these m subarrays.

Example 1:

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.

Example 2:

Input: nums = [1,2,3,4,5], m = 2
Output: 9

Example 3:

Input: nums = [1,4,4], m = 3
Output: 4

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 106
  • 1 <= m <= min(50, nums.length)

題目輸入一個非排序後的純數值陣列 nums,以及可分割的數量 m。我們要做的就是將陣列分割成 m 個子陣列,並讓子陣列中加總最大的值保證在所有分割可能中是最小的。


解題思路

由於接種疫苗因素,本日無更詳細的解法解釋

二元搜索解法

我有看到討論區有 DP 的解法… 但我實在沒心力去解出來,只有想出用二元搜索的方式來解題。

二元搜索的邊界中,最小的左值應為陣列中的最大值,因為每單一值為一個子陣列通常是最小的切法(雖然根據題目中給予的 m 會導致我們很難做到這一點)。

最大的右值應為整個陣列加總,因為整個陣列就是一個子陣列就會是最糟的情況。

決定好邊界值後,接下來就是進行經典二元搜索了。二元搜索中我額外建立了一個函式 canSplit() 來判斷這樣是否可切成 m 個子陣列。

當子陣列中的加總值大於當前我們判斷的中間值時,即需要切割出新的子陣列 —— 因為我們需要最大的加總值不要超過當前判斷的中間值。

而一但需要切割的次數多了,超過題目設定的 m 個子陣列時,則代表當前設定的最大值太小了,導致需要切太多的子陣列,所以這時我們就需要提高我們的最小的邊界值左值,來讓我們可以考慮更大的中間值(子陣列中加總的最大值)。

而一但確定當前的中間值可以切割,則我們就可以更貪婪地將最大邊界值右值縮小為中間值減一,來找到更小的最大值。

有點繞口,頭腦開始昏昏沉沉的了,還是直接看程式碼吧!



二元搜索法 C++ 範例程式碼

class Solution {
public:
    bool canSplit(vector<int>& nums, int m, int curr) {
        // Init
        int count = 1;
        int sum = 0;
        
        // Try to split
        for (int n: nums) {
            if (sum + n <= curr) {
                sum += n;
            }
            else {
                sum = n;
                ++count;
                
                if (count > m) return false;
            }            
        }
        
        return true;
    }
    
    int splitArray(vector<int>& nums, int m) {
        // Init
        int left = 0;
        int right = 0;
        
        // Determine the left and right boundary
        for (auto& n: nums) {
            right += n;
            left = max(left, n);
        }
        
        // Assign the worse case to initialize ans
        int ans = right;
        
        // Binary search
        while (left <= right) {
            int mid = left + (right-left) / 2;
            
            // If the mid number can split, try to find the more little sum
            if (canSplit(nums, m, mid)) {
                ans = min(ans, mid);
                right = mid - 1;
            }
            
            // If mid number cannot split, try to find the larger sum
            else {
                left = mid + 1;
            }
        }
        
        return ans;
    }
};

References


Read More

Leave a Reply取消回覆

Exit mobile version