寻找最大和的连续子序列：兼顾长度的Java实现

心靈之曲

发布时间：2025-10-29 16:30:10

896人浏览过

来源于php中文网

原创

寻找最大和的连续子序列：兼顾长度的java实现

本文旨在提供一个清晰易懂的Java教程，用于寻找列表中元素之和最大的连续子序列，并在存在多个和相同的子序列时，返回长度最长的那个。我们将详细解释算法逻辑，并提供可直接运行的代码示例，帮助读者理解并应用该算法。

在编程中，经常会遇到需要寻找数组或列表中特定子序列的问题。其中一个经典问题是：如何找到一个连续子序列，使其元素之和最大？更进一步，如果存在多个和相同的最大子序列，我们又该如何选择长度最长的那个呢？本文将提供一个Java实现的解决方案。

算法思路

解决这个问题的关键在于使用 Kadane 算法的变体。Kadane 算法用于查找数组中最大和的连续子数组。为了满足“长度最长”的条件，我们需要在找到相同和的子序列时，比较它们的长度，并保留长度更长的那个。

具体步骤如下：

晓象AI资讯阅读神器

晓象-AI时代的资讯阅读神器

下载

立即学习“Java免费学习笔记（深入）”；

初始化：
- maxSumStartIndex: 最大和子序列的起始索引。
- maxSumLastIndex: 最大和子序列的结束索引。
- maxSum: 最大和。
- maxSumLength: 最大和子序列的长度。
- lastSumStartIndex: 当前正在计算的子序列的起始索引。
- lastSum: 当前正在计算的子序列的和。
遍历列表： 从列表的第二个元素开始遍历。
更新当前子序列的和： lastSum += list.get(i)。
如果当前子序列的和小于当前元素： 说明从当前元素开始新的子序列可能得到更大的和。因此，重置 lastSum 为当前元素，并更新 lastSumStartIndex。
如果当前子序列的和大于最大和： 更新 maxSumStartIndex，maxSumLastIndex，maxSumLength 和 maxSum。
如果当前子序列的和等于最大和： 比较当前子序列的长度和 maxSumLength。如果当前子序列更长，则更新 maxSumStartIndex，maxSumLastIndex 和 maxSumLength。
遍历结束后： maxSumStartIndex 和 maxSumLastIndex 指向的就是最大和且长度最长的连续子序列的起始和结束索引。

Java 代码示例

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

public class MaxSumSubsequence {

    public static void main(String[] args) {
        List list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(-5);
        list.add(6);
        list.add(-3);
        list.add(-13434);
        list.add(99);
        list.add(99);
        list.add(-444);
        list.add(-7444);
        list.add(100);
        list.add(90);
        list.add(8);

        if (list == null || list.isEmpty()) {
            System.out.println("empty array");
            return;
        }

        int maxSumStartIndex = 0;
        int maxSumLastIndex = 0;
        int maxSum = list.get(0);
        int maxSumLength = 1; // 初始长度为1

        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;
                maxSumLength = maxSumLastIndex - maxSumStartIndex + 1;
                maxSum = lastSum;
            } else if (maxSum == lastSum) {
                if (i - lastSumStartIndex + 1 > maxSumLength) {
                    maxSumStartIndex = lastSumStartIndex;
                    maxSumLastIndex = i;
                    maxSumLength = i - lastSumStartIndex + 1;
                }
            }
        }

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