P410 Split Array Largest Sum

Analysis

Solution 1: DP

假设这是一个动态规划题; 下面设计状态和状态转移方程.

状态定义: f[i][j], 前i个元素, 被切成j个子数组, 且最后一个子数组以元素i结尾, 所产生的最小的最大子数组和的值

设p为nums的前缀和数组.

初始状态:

f[1][1] = p[1]
f[2][1] = p[2]
f[i][1] = p[i]

转移方程

f[i][j] = f[i][j].min(f[k][j - 1].max(p[i] - p[x]))

由于f[i][j]只与f[k][j-1]有关, 因此可以进行空间压缩.

复杂度: O(kn^2)/O(n)

Solution 2: Binary Search

"使...的最大值尽可能小"是二分搜索题目常见的问法.

复杂度: O(nlog(sum - maxn))/O(1)

Code

rust

/// get ans in O(n^2)/O(n)
pub fn split_array(nums: Vec<i32>, k: i32) -> i32 {
    let n = nums.len();
    let k = k as usize;

    // find the prefix sum of array nums
    let mut p = vec![0; n + 1];
    for i in 0..n {
        p[i + 1] = p[i] + nums[i];
    }

    // dp
    let mut f = vec![i32::MAX; n + 1];
    // init state
    for i in 1..=n {
        f[i] = p[i];
    }
    // iteration
    for j in 2..=k {
        for i in (2..=n).rev() {
            for x in (j-1)..i {
                f[i] = f[i].min(f[x].max(p[i] - p[x]));
            }
        }
    }
    f[n]
}

c

// 最多拆分为k个子数组, 且每个子数组的和不超过x
bool canSplit(int* nums, int numsSize, int k, int x);

int splitArray(int* nums, int numsSize, int k) {
    int64_t l = 0, r = 0;
    for (int i = 0; i < numsSize; ++i) {
        r += nums[i]; // sum of nums
        if (l < nums[i]) l = nums[i]; // max of nums
    }

    while (l < r) {
        int64_t mid = (l + r) >> 1;
        if (canSplit(nums, numsSize, k, mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    return l;
}

// O(n)/O(1)
bool canSplit(int* nums, int numsSize, int k, int x) {
    int64_t sum = 0;
    int cnt = 1;
    for (int i = 0; i < numsSize; ++i) {
        if (sum + nums[i] > x) {
            cnt += 1;
            sum = nums[i];
        } else {
            sum += nums[i];
        }
    }
    return cnt <= k;
}