> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/partition/410.-split-array-largest-sum.md).

# 410. Split Array Largest Sum

对由非负数组成的数组划分成给定的m份，最小化和最大的子数组。解这种给定背包数，找能把物品（质量值为正数）一一全部放进去的背包最小容量的题用二分最快。对每个二分mid时检查mid是否能让数组在m次分完，当需要的次数大于D时说明mid取小了，start + 1。

```cpp
/*
 * @lc app=leetcode id=410 lang=cpp
 *
 * [410] Split Array Largest Sum
 */
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        const auto check = [](vector<int>& weights, long mid) {
            long sum = 0, c = 1;
            for (int w : weights) {
                if (sum + w > mid) {
                    sum = 0;
                    ++c;
                } 
                sum += w;
            }
            return c;
        };
        long start = 1, end = 1;
        for (int w : nums) {
            start = max(start, (long) w);
            end += w;
        }
        while (start < end) {
            long mid = start + (end - start) / 2;
            if (m < check(nums, mid)) {
                start = mid + 1;
            } else {
                end = mid;
            }    
        }
        return start;
    }
};


```

partition + optimal用DP。action为对让当前num\[j]分别和不同的前面的元素k组成一个划分\[k+1, j]，受限于前面的划分数目。因此把划分数encoding进状态，题目所求encoding进值，dp\[i]\[j]表示从0到j形成i个划分的最优解，前面\[0, k]有i - 1个划分，即dp\[i - 1]\[k]。三重循环。

代码参考了花花的。

```cpp
/*
 * @lc app=leetcode id=410 lang=cpp
 *
 * [410] Split Array Largest Sum
 *
 * https://leetcode.com/problems/split-array-largest-sum/description/
 *
 * algorithms
 * Hard (42.82%)
 * Likes:    954
 * Dislikes: 53
 * Total Accepted:    53.5K
 * Total Submissions: 124.8K
 * Testcase Example:  '[7,2,5,10,8]\n2'
 *
 * Given an array 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.
 * 
 * 
 * Note:
 * If n is 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.
 * 
 * 
 */
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        const int N = nums.size();
        vector<long> sums(N);
        sums[0] = nums[0];
        for (int j = 1; j < N; ++j) {
            sums[j] = sums[j - 1] + nums[j];
        }
        vector<vector<long>> dp(m + 1, vector<long>(N, INT_MAX));
        for (int j = 0; j < N; ++j) dp[1][j] = sums[j];
        for (int i = 2; i <= m; ++i) {
            for (int j = 0; j < N; ++j) {
                for (int k = 0; k < j; ++k) {
                    dp[i][j] = min(dp[i][j], max(dp[i - 1][k], sums[j] - sums[k]));
                }
            }
        }
        return dp[m][N - 1];
    }
};


```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/partition/410.-split-array-largest-sum.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.