前言

想要精通算法和SQL的成長(zhǎng)之路 - 系列導(dǎo)航

一. 分割數(shù)組的最大值

原題鏈接

首先面對(duì)這個(gè)題目，我們可以捕獲幾個(gè)關(guān)鍵詞：

• 非負(fù)整數(shù)。
• 非空連續(xù)子數(shù)組。

那么我們假設(shè)分割后的子數(shù)組，和的最大值是M，對(duì)應(yīng)分割的子數(shù)組個(gè)數(shù)為N。他們之間必然存在以下關(guān)系：

• 分割的子數(shù)組個(gè)數(shù) N 越多，對(duì)應(yīng)的和最大值 M 也就越小。
• 分割的子數(shù)組個(gè)數(shù) N 越少，對(duì)應(yīng)的和最大值 M 也就越大。

那么我們以每組和的最大值作為切入點(diǎn)，案例如下：

• 設(shè)置 數(shù)組各自和的最大值 為 20，此時(shí)分割依然是 [7, 2, 5, | 10, 8]，此時(shí)分割的數(shù)組數(shù)為2。
• 設(shè)置 數(shù)組各自和的最大值 為 19，此時(shí)分割依然是 [7, 2, 5, | 10, 8]，此時(shí)分割的數(shù)組數(shù)為2。
• 設(shè)置 數(shù)組各自和的最大值 為 18，此時(shí)分割依然是 [7, 2, 5, | 10, 8]，此時(shí)分割的數(shù)組數(shù)為2。
• 設(shè)置 數(shù)組各自和的最大值 為 17，此時(shí)分割就變成了 [7, 2, 5, | 10, | 8]，此時(shí)分割的數(shù)組數(shù)為3。

而我們題目要求分割組數(shù)是2，那么滿(mǎn)足這個(gè)條件的幾種情況，我們?cè)偃∽畲蠛妥钚〉那闆r，最終得到結(jié)果是18。

1.1 二分法

二分的目標(biāo)對(duì)象是什么？我們可以二分：數(shù)組各自和的最大值。那么二分法，就應(yīng)該有初始區(qū)間：

• left：可以是當(dāng)前數(shù)組的最大元素值。（單個(gè)元素一組）
• right：可以是當(dāng)前數(shù)組的總和。（所有元素成一組）

那么我們二分后取得 mid：

int mid = left + (right - left) / 2;

接下來(lái)我們就要對(duì)數(shù)組進(jìn)行分組計(jì)算了，對(duì)數(shù)組從左往右按順序分組，使得分組后的各個(gè)子數(shù)組和不能超過(guò)mid。我們可以編寫(xiě)個(gè)helper函數(shù)：

public int helper(int[] nums, int maxGroupSum) {
    // 分組數(shù)最小是1
    int res = 1;
    int curSum = 0;
    for (int num : nums) {
        // 如果加入當(dāng)前元素會(huì)導(dǎo)致和超過(guò)限制，那么就另外再分一組
        if (curSum + num > maxGroupSum) {
            res++;
            curSum = 0;
        }
        curSum += num;
    }
    return res;
}

我們計(jì)算好分組后的個(gè)數(shù)groupNum之后，就需要和題目傳入的k進(jìn)行對(duì)比：

• groupNum > k ： 說(shuō)明數(shù)組各自和的最大值還是小了，我們應(yīng)該調(diào)大數(shù)組各自和的最大值。即left = mid +1。
• 反之：right = mid;

最終代碼如下：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-725422.html

public int splitArray(int[] nums, int k) {
    int max = 0, sum = 0;
    for (int num : nums) {
        max = Math.max(max, num);
        sum += num;
    }
    int left = max, right = sum;
    while (left < right) {
        int mid = left + (right - left) / 2;
        // 如果分組數(shù)比 k 還要大，說(shuō)明每個(gè)分組的和最大值還是小了
        int groupNum = helper(nums, mid);
        if (groupNum > k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

public int helper(int[] nums, int maxGroupSum) {
    // 分組數(shù)最小是1
    int res = 1;
    int curSum = 0;
    for (int num : nums) {
        // 如果加入當(dāng)前元素會(huì)導(dǎo)致和超過(guò)限制，那么就另外再分一組
        if (curSum + num > maxGroupSum) {
            res++;
            curSum = 0;
        }
        curSum += num;
    }
    return res;
}

到了這里，關(guān)于想要精通算法和SQL的成長(zhǎng)之路 - 分割數(shù)組的最大值的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！