动态规划分割数组求最小差：负数数组场景失效问题求助

问题描述 #

目标是将包含2n个整数的数组分割为两个长度为n的子数组，最小化两数组和的绝对差。当前实现的动态规划解法在正整数数组中有效，但在负数数组测试用例中失效：

• 测试用例：输入nums = [2,-1,0,4,-2,-9]
• 正确输出：0（最优分割为[2,4,-9]和[-1,0,-2]，两数组和的绝对差为0）
• 当前代码输出：6

已知问题：已能获取负数数组的可能子集和并存储在记忆化Map列表中，但遍历Map计算绝对差时逻辑出错——记忆化Map中存在子集和-3，计算时得到差值6而非正确的0。

原问题代码 #

package com.dynamicProgramming;

import java.util.*;

public class PartitionSum {

    List<HashMap<Integer,Boolean>> ll = new ArrayList<>();

    public int minimumDifference(int[] nums) {
        int n = nums.length;
        int range = 0;
        for(int i =0;i<nums.length;i++){
            ll.add(new HashMap<>());
            range+=nums[i];
        }
       // System.out.println(range/2);
        findSub(nums ,n-1,range);
       int min=Integer.MAX_VALUE;
//Code that needs to re-vistied for negative integers scenario
       for(HashMap<Integer,Boolean> h:ll){

           for(Map.Entry<Integer,Boolean> map:h.entrySet()){

               if(map.getValue()){

                   int s2= (range<0)?range+map.getKey():range-map.getKey();

                   System.out.println(map.getKey()+ " "+s2);
                   int diff=Math.abs(s2-map.getKey());
                   min=Math.min(min,diff);
               }
           }
       }
        return min;
    }

    private boolean findSub(int[] nums, int i, int sum) {

        if(sum==0)
            return true;
        if(i==0){
            return nums[i]==sum;
        }

        if(ll.get(i).containsKey(sum)) {
            return ll.get(i).get(sum);

        }
        boolean p=false;
        if(sum>=nums[i])
            p=findSub(nums,i-1,sum-nums[i]);
        boolean np=findSub(nums,i-1,sum);
        ll.get(i).put(sum,p||np);
        return p||np;


    }


    public static void main(String[] args) {
        PartitionSum partitionSum= new PartitionSum();
        int[] nums={2,-1,0,4,-2,-9};

        System.out.println(partitionSum.minimumDifference(nums));
        System.out.println(partitionSum.ll);
    }

}

错误原因分析 #

1. 未限制子集长度：题目要求分割为两个长度为n的子数组，但原代码未记录子集的元素个数，导致遍历了所有长度的子集和，而非仅长度为n的。
2. 负数场景下的选择逻辑错误：findSub中sum>=nums[i]的判断会过滤掉选择负数元素的情况（比如sum=-5、nums[i]=-3时，sum >= nums[i]不成立，跳过选择该元素），导致漏算大量有效子集和。
3. 差值计算逻辑错误：原代码中s2的计算方式错误，无论数组总和正负，另一个子集的和应为totalSum - 当前子集和，两子集的绝对差应为Math.abs(totalSum - 2 * 当前子集和)。

修正后的代码 #

package com.dynamicProgramming;

import java.util.*;
import java.util.stream.*;

public class PartitionSum {

    // dp[i] 存储处理前i个元素时，不同子集长度对应的所有可能和
    List<Map<Integer, Set<Integer>>> dp = new ArrayList<>();

    public int minimumDifference(int[] nums) {
        int subLen = nums.length / 2; // 每个子集必须包含的元素个数
        int totalSum = Arrays.stream(nums).sum();
        int arrLen = nums.length;

        // 初始化：处理0个元素时，仅存在长度为0、和为0的子集
        dp.add(new HashMap<>());
        dp.get(0).put(0, new HashSet<>());
        dp.get(0).get(0).add(0);

        for (int i = 1; i <= arrLen; i++) {
            dp.add(new HashMap<>());
            int currentNum = nums[i - 1];
            // 复制上一个状态（不选当前元素）
            for (Map.Entry<Integer, Set<Integer>> entry : dp.get(i - 1).entrySet()) {
                int sum = entry.getKey();
                Set<Integer> counts = entry.getValue();
                dp.get(i).putIfAbsent(sum, new HashSet<>());
                dp.get(i).get(sum).addAll(counts);
            }
            // 更新选择当前元素后的状态
            for (Map.Entry<Integer, Set<Integer>> entry : dp.get(i - 1).entrySet()) {
                int sum = entry.getKey();
                Set<Integer> counts = entry.getValue();
                int newSum = sum + currentNum;
                dp.get(i).putIfAbsent(newSum, new HashSet<>());
                for (int cnt : counts) {
                    dp.get(i).get(newSum).add(cnt + 1);
                }
            }
        }

        int minDiff = Integer.MAX_VALUE;
        // 仅遍历长度为subLen的子集和，计算最小差值
        Map<Integer, Set<Integer>> finalState = dp.get(arrLen);
        for (Map.Entry<Integer, Set<Integer>> entry : finalState.entrySet()) {
            int sum = entry.getKey();
            Set<Integer> counts = entry.getValue();
            if (counts.contains(subLen)) {
                int diff = Math.abs(totalSum - 2 * sum);
                minDiff = Math.min(minDiff, diff);
            }
        }
        return minDiff;
    }

    public static void main(String[] args) {
        PartitionSum partitionSum = new PartitionSum();
        int[] nums = {2, -1, 0, 4, -2, -9};
        System.out.println(partitionSum.minimumDifference(nums)); // 输出0
    }
}

修正说明 #

1. 新增子集长度维度：动态规划状态同时记录子集的长度和对应的和，确保只考虑长度为n的子集。
2. 移除负数选择限制：不再通过sum>=nums[i]过滤选择逻辑，保证负数元素能被正常选入子集。
3. 修正差值计算：使用Math.abs(totalSum - 2 * sum)计算两子集和的绝对差，逻辑更准确。

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