如何修正Java最大和子序列代码，优先返回首个等长等和序列？

问题说明 #

我编写了一个Java程序用于寻找元素和最大的子序列，规则如下：

• 若存在多个和相同但元素数量不同的序列，输出元素最少的
• 若存在2个及以上和相同且元素数量相同的序列，需返回列表中最先出现的序列

但当前程序返回的是最后一个符合条件的序列，预期输出为100 98，实际输出为99 99。

原代码 #

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(-9999);
        list.add(-9999);
        list.add(100);//索引4
        list.add(98);//索引5
        list.add(-5555);
        list.add(99);
        list.add(99);
        list.add(-7866);
        list.add(6);
        list.add(-3);
        list.add(-13434);
        list.add(99);//索引13
        list.add(90);
        list.add(8);
        list.add(1);//索引16
        list.add(-9999);
        //list.add(99);//11
        //list.add(99);//12
        list.add(-9999);
        //list.add(198);
        list.add(-444);
        list.add(-7444);
        list.add(100);
        list.add(90);
        list.add(8);
        list.add(-9999);
        //list.add(100);
        //list.add(98);
        list.add(-5555);
        
        if (list == null || list.size() == 0) {//检查列表是否为空
            System.out.println("empty array");
            return;
        }

        int maxSumStartIndex = 0;
        int maxSumLastIndex = 0;
        int maxSum = list.get(0);

        int lastSumStartIndex = 0;
        int lastSum = list.get(0);

        for (int i = 1; i < list.size(); i++) {

            lastSum += list.get(i);
            if (lastSum < list.get(i)) {
                lastSum = list.get(i);
                lastSumStartIndex = i;
            }

            if (maxSum < lastSum) {
                maxSumStartIndex = lastSumStartIndex;
                maxSumLastIndex = i;
                maxSum = lastSum;
            }
            if (maxSum == lastSum) {
                if (maxSumLastIndex - maxSumStartIndex < i - lastSumStartIndex) continue;//用于保留最短长度
                maxSumStartIndex = lastSumStartIndex;
                maxSumLastIndex = i;
            }
        }

        System.out.println("sum( arr[" + maxSumStartIndex + "] .. arr[" + maxSumLastIndex + "] ) = " + maxSum);
        for (int i = maxSumStartIndex; i <= maxSumLastIndex; i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}

问题根源 #

原代码在处理和相同的序列时，判断逻辑错误：只要新序列的长度不小于当前最大序列的长度，就会更新最大序列的索引。这导致后续出现的同长度同和序列会覆盖掉之前最先出现的序列。

修复方案 #

修改maxSum == lastSum的判断逻辑，仅当新序列的长度更短时才更新最大序列；若长度相同，则保留最先出现的序列，不做更新。

修复后的关键代码块：

if (maxSum == lastSum) {
    int currentSeqLength = maxSumLastIndex - maxSumStartIndex + 1;
    int newSeqLength = i - lastSumStartIndex + 1;
    // 仅当新序列长度更短时才更新，长度相同则保留最早出现的序列
    if (newSeqLength < currentSeqLength) {
        maxSumStartIndex = lastSumStartIndex;
        maxSumLastIndex = i;
    }
}

修复后完整代码 #

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(-9999);
        list.add(-9999);
        list.add(100);//索引4
        list.add(98);//索引5
        list.add(-5555);
        list.add(99);
        list.add(99);
        list.add(-7866);
        list.add(6);
        list.add(-3);
        list.add(-13434);
        list.add(99);//索引13
        list.add(90);
        list.add(8);
        list.add(1);//索引16
        list.add(-9999);
        //list.add(99);//11
        //list.add(99);//12
        list.add(-9999);
        //list.add(198);
        list.add(-444);
        list.add(-7444);
        list.add(100);
        list.add(90);
        list.add(8);
        list.add(-9999);
        //list.add(100);
        //list.add(98);
        list.add(-5555);
        
        if (list == null || list.size() == 0) {//检查列表是否为空
            System.out.println("empty array");
            return;
        }

        int maxSumStartIndex = 0;
        int maxSumLastIndex = 0;
        int maxSum = list.get(0);

        int lastSumStartIndex = 0;
        int lastSum = list.get(0);

        for (int i = 1; i < list.size(); i++) {

            lastSum += list.get(i);
            if (lastSum < list.get(i)) {
                lastSum = list.get(i);
                lastSumStartIndex = i;
            }

            if (maxSum < lastSum) {
                maxSumStartIndex = lastSumStartIndex;
                maxSumLastIndex = i;
                maxSum = lastSum;
            }
            if (maxSum == lastSum) {
                int currentSeqLength = maxSumLastIndex - maxSumStartIndex + 1;
                int newSeqLength = i - lastSumStartIndex + 1;
                // 仅当新序列长度更短时才更新，长度相同则保留最早出现的序列
                if (newSeqLength < currentSeqLength) {
                    maxSumStartIndex = lastSumStartIndex;
                    maxSumLastIndex = i;
                }
            }
        }

        System.out.println("sum( arr[" + maxSumStartIndex + "] .. arr[" + maxSumLastIndex + "] ) = " + maxSum);
        for (int i = maxSumStartIndex; i <= maxSumLastIndex; i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}

验证结果 #

修复后程序会输出预期的100 98，符合规则中“同和同长度时返回最先出现序列”的要求。

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