数组连续分割后的最小子数组值总和求解及Java实现咨询

我来帮你拆解这个问题，先把核心逻辑理清楚，再一步步给出可运行的Java实现：

问题转化（关键！） #

题目里每个子数组的“值”是子数组总和减去其中最小的c个元素的和。如果我们把所有子数组的“值”加起来，会发现一个非常有用的转化：

总价值 = 整个数组的总和 - 所有子数组中最小c个元素的和的总和

因为分割后的所有子数组的元素总和加起来就是原数组的总和（每个元素只属于一个子数组）。所以，最小化总价值等价于最大化所有子数组中最小c个元素的和的总和——这个转化让我们的目标更清晰：尽可能让更多元素被计入“子数组的最小c个元素”中，从而减少总价值。

动态规划思路 #

我们用dp[i]表示前i个元素（对应原数组的0到i-1索引）能得到的最大贡献总和（也就是所有子数组最小c个元素的和的总和）。

递推关系 #

对于dp[i]，我们需要考虑两种情况：

1. 最后一个子数组长度≤c：此时这个子数组的所有元素都属于“最小c个元素”，贡献就是这个子数组的总和。我们遍历所有可能的子数组长度t（1到min(c, i)），取dp[i-t] + 子数组总和的最大值。
2. 最后一个子数组长度>c：此时这个子数组的贡献是其中最小c个元素的和。我们遍历所有可能的子数组长度t（c+1到i），取dp[i-t] + 子数组最小c个元素的和的最大值。

最终，总最小价值就是原数组总和 - dp[n]（n是原数组长度）。

Java实现代码 #

完整可运行代码 #

import java.util.ArrayList;
import java.util.Collections;

public class MinSplitValue {
    public static void main(String[] args) {
        int[] a = {3, 1, 6, 5, 2};
        int c = 2;
        int result = minTotalValue(a, c);
        System.out.println("最小总价值：" + result); // 输出6，对应分割为[3,1,6]和[5,2]的情况
    }

    public static int minTotalValue(int[] a, int c) {
        int n = a.length;
        if (n == 0) return 0;

        // 计算前缀和：prefixSum[i]是前i个元素的和（a[0]到a[i-1]）
        long[] prefixSum = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            prefixSum[i] = prefixSum[i - 1] + a[i - 1];
        }

        // 预处理sum_c_smallest[j][i]：a[j..i]的最小c个元素的和
        long[][] sum_c_smallest = new long[n][n];
        for (int i = 0; i < n; i++) {
            ArrayList<Integer> tempList = new ArrayList<>();
            for (int j = i; j >= 0; j--) {
                tempList.add(a[j]);
                // 排序后取最小的c个元素求和
                Collections.sort(tempList);
                int take = Math.min(c, tempList.size());
                long sum = 0;
                for (int k = 0; k < take; k++) {
                    sum += tempList.get(k);
                }
                sum_c_smallest[j][i] = sum;
            }
        }

        // dp[i]表示前i个元素的最大贡献总和
        long[] dp = new long[n + 1];
        // 初始化：dp[0]为0，其他设为负无穷（表示初始不可达）
        for (int i = 1; i <= n; i++) {
            dp[i] = Long.MIN_VALUE;
        }
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            // 情况1：最后一个子数组长度<=c
            int maxT = Math.min(c, i);
            for (int t = 1; t <= maxT; t++) {
                int prev = i - t;
                if (dp[prev] != Long.MIN_VALUE) {
                    long current = dp[prev] + (prefixSum[i] - prefixSum[prev]);
                    dp[i] = Math.max(dp[i], current);
                }
            }

            // 情况2：最后一个子数组长度>c
            int minT = c + 1;
            if (minT <= i) {
                for (int t = minT; t <= i; t++) {
                    int j = i - t;
                    if (dp[j] != Long.MIN_VALUE) {
                        // 子数组对应a[j..i-1]
                        long sumC = sum_c_smallest[j][i - 1];
                        long current = dp[j] + sumC;
                        dp[i] = Math.max(dp[i], current);
                    }
                }
            }
        }

        // 总最小价值 = 数组总和 - 最大贡献总和
        return (int) (prefixSum[n] - dp[n]);
    }
}

代码说明 #

1. 前缀和：用来快速计算任意子数组的总和，避免重复计算，提升效率。
2. 预处理最小c元素和：通过遍历每个子数组，排序后取前c个元素求和。这个方法的时间复杂度是O(n² log n)，对于中小规模的数组（比如n≤1000）完全够用。
3. 动态规划数组：初始化时将非0位置设为负无穷，确保只有可达的状态被考虑。遍历两种情况，取最大值更新dp[i]。

优化方向 #

如果需要处理更大规模的数组（比如n≥1e4），O(n²)的时间复杂度就不够了。这时候可以考虑用以下方法优化：

• 用滑动窗口维护最近c个dp[j] - prefixSum[j]的最大值，优化情况1的计算，把这部分时间降到O(n)。
• 用两个堆（最大堆存最小c个元素，最小堆存剩余元素）动态维护子数组的最小c元素和，优化情况2的计算，把这部分时间降到O(n log n)。

内容的提问来源于stack exchange，提问作者Squeez