题解 | #分组#

思路：

题目的主要信息：

• 数组a有n个元素，将其分成k个连续的子序列
• 求最大的每个子序列和最小值

方法一：暴力判断
具体做法：
我们都知道子序列和最小值绝不会超过数组a的元素和sum，同时分成k组后，也绝不会大于，因此我们可以从开始，依次递减判断每个数是否成为k组连续子序列和的最小值。
在判断的时候，我们累加a数组中的元素，每次超过我们要判断的数时，就计数代表一段，同时累加归零往后重新累加。如果最后我们的分段数大于等于m，即认为这是可行的分段，也是当前找到的最大最小和。

class Solution {
public:
    bool judge(vector<int>& a, int k, int n){
        int sum = 0;
        int count = 0;
        for(int i = 0; i < a.size(); i++){
            sum += a[i];
            if(sum >= n){ //找到每一个大于n的连续分段和
                sum = 0;
                count++; //段数
            }
            if(count >= k) //分段数大于等于k
                return true;
        }
        return false;
    }
    int solve(int n, int k, vector<int>& a) {
        int sum = 0;
        for(int i = 0; i < n; i++)
            sum += a[i];  
        if(k == 1)  //只有一个分组
            return sum;
        int i = sum / k;  //最大可能
        for(; i >= 0; i--){
            if(judge(a, k, i))  //判断mid是否有k个分组
                return i;
        }
        return i;
    }
};

复杂度分析：

• 时间复杂度：，外循环最坏情况循环从最大到零，judge函数每次判断都是，外面累加函数第次幂忽略不计
• 空间复杂度：，只有常数个变量

方法二：二分法
具体做法：
因为上述方法一也是从一个有序序列中找到第一个符合情况的元素，这非常类似数组中的二分查找，因此我们可以使用二分对其改进：
左边界初始为0，右边界初始为，每次判断中值是否符合条件，判断函数同方法一，如果符合条件，我们左边界右移，如果不符合我们右边界左移，直至二者相等或左大于右。
如图解所示：

class Solution {
public:
    bool judge(vector<int>& a, int k, int n){
        int sum = 0;
        int count = 0;
        for(int i = 0; i < a.size(); i++){
            sum += a[i];
            if(sum >= n){ //找到每一个大于n的连续分段和
                sum = 0;
                count++; //段数
            }
            if(count >= k) //分段数大于等于k
                return true;
        }
        return false;
    }
    int solve(int n, int k, vector<int>& a) {
        int left = 0, right = 0;
        for(int i = 0; i < n; i++)
            right += a[i];  //right最大为数组和
        right /= k;
        while(left < right){ //二分法
            int mid = (left + right + 1) / 2;
            if(judge(a, k, mid)) //判断mid是否有k个分组
                left = mid;
            else
                right = mid - 1;
        }
        return left;
    }
};

复杂度分析：

• 时间复杂度：，二分法将外循环缩小到其对数运算，其余同方法一
• 空间复杂度：，常数个变量