Java实现：带优先级规则的最大子序列求和算法

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

public class MaxSubsequenceWithPriorities {

    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 -> 子序列 [100, 98], 和 198, 长度 2
        list.add(-5555);
        list.add(99);  // 索引 7
        list.add(99);  // 索引 8 -> 子序列 [99, 99], 和 198, 长度 2
        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); list.add(-9999);
        list.add(-9999); list.add(-444); list.add(-7444);
        list.add(100); // 索引 22
        list.add(90);  // 索引 23
        list.add(8);   // 索引 24 -> 子序列 [100, 90, 8], 和 198, 长度 3
        list.add(-9999); list.add(-5555);

        // 处理空列表或单元素列表的边界情况
        if (list == null || list.isEmpty()) {
            System.out.println("输入列表为空。");
            return;
        }

        // 初始化最大和及其对应的子序列索引
        int maxSum = list.get(0);
        int maxSumStartIndex = 0;
        int maxSumLastIndex = 0;

        // 初始化当前子序列的和及其起始索引
        int currentSum = list.get(0);
        int currentStartIndex = 0;

        // 遍历列表，从第二个元素开始
        for (int i = 1; i < list.size(); i++) {
            // 更新 currentSum 和 currentStartIndex
            // 如果当前元素比 (currentSum + 当前元素) 更大，意味着从当前元素开始一个新的子序列会更好
            if (currentSum + list.get(i) < list.get(i)) {
                currentSum = list.get(i);
                currentStartIndex = i;
            } else {
                // 否则，将当前元素加入到 currentSum
                currentSum += list.get(i);
            }

            // 比较当前子序列与全局最佳子序列
            if (currentSum > maxSum) {
                // 找到了更大的和，直接更新
                maxSum = currentSum;
                maxSumStartIndex = currentStartIndex;
                maxSumLastIndex = i;
            } else if (currentSum == maxSum) {
                // 和相等，应用优先级规则
                int currentBestLength = maxSumLastIndex - maxSumStartIndex + 1;
                int newLength = i - currentStartIndex + 1;

                if (newLength < currentBestLength) {
                    // 新子序列长度更短，根据规则1，优先选择
                    maxSumStartIndex = currentStartIndex;
                    maxSumLastIndex = i;
                    // maxSum 保持不变，因为和相等
                }
                // 如果 newLength == currentBestLength，根据规则2，我们希望保留最先出现的。
                // 由于我们只在严格更好或更短时更新，这里不进行操作，就隐式地保留了最先找到的。
            }
        }

        // 输出结果
        System.out.println("最大子序列的和为: " + maxSum);
        System.out.print("对应的子序列为: ");
        for (int i = maxSumStartIndex; i <= maxSumLastIndex; i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
        System.out.println("起始索引: " + maxSumStartIndex + ", 结束索引: " + maxSumLastIndex);
    }
}

最大子序列的和为: 198
对应的子序列为: 100 98 
起始索引: 4, 结束索引: 5