首页 > Java > java教程 > 正文

如何找出列表中元素和最大的最长连续子序列?

心靈之曲
发布: 2025-10-29 14:33:01
原创
724人浏览过

如何找出列表中元素和最大的最长连续子序列?

本文旨在提供一个清晰的Java教程,指导读者如何在一个整数列表中找到元素和最大的最长连续子序列。我们将深入研究 Kadane 算法的变体,以满足寻找最长子序列的特定需求。通过提供的代码示例,读者将能够理解并实现该算法,并应用于实际编程场景中。

在处理数据时,经常需要从一个列表中找到满足特定条件的子序列。一个常见的需求是找到元素和最大的连续子序列。更进一步,如果存在多个和相同的子序列,我们需要找出其中最长的那个。本文将提供一个Java实现,用于解决这个问题。

算法思路

解决此问题的关键在于Kadane算法的变体。Kadane算法用于查找最大子数组和,而我们的目标是在此基础上,如果存在多个具有相同最大和的子数组,则选择最长的那个。

核心思想是维护两个变量:lastSum 和 maxSum。lastSum 跟踪到当前位置为止的子序列和,而 maxSum 存储迄今为止找到的最大子序列和。此外,我们还需要跟踪子序列的起始和结束索引,以及子序列的长度。

Java 代码实现

以下是Java代码的实现,它扩展了Kadane算法以找到最长的最大和子序列:

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

public class MaxSumSubsequence {

    public static void main(String[] args) {
        List<Integer> 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();
    }
}
登录后复制

代码解释

  1. 初始化:

    序列猴子开放平台
    序列猴子开放平台

    具有长序列、多模态、单模型、大数据等特点的超大规模语言模型

    序列猴子开放平台0
    查看详情 序列猴子开放平台
    • maxSumStartIndex, maxSumLastIndex: 分别存储最大和子序列的起始和结束索引。
    • maxSum: 存储当前找到的最大子序列和。
    • maxSumLength: 存储最大和子序列的长度。
    • lastSumStartIndex: 存储当前计算的子序列的起始索引。
    • lastSum: 存储当前计算的子序列和。
  2. 循环遍历:

    • 从列表的第二个元素开始循环。
    • lastSum += list.get(i): 将当前元素添加到当前子序列和。
    • if (lastSum < list.get(i)): 如果当前子序列和小于当前元素,则从当前元素开始新的子序列。
    • if (maxSum < lastSum): 如果当前子序列和大于当前最大和,则更新最大和及相关索引和长度。
    • else if (maxSum == lastSum): 如果当前子序列和等于当前最大和,则比较长度,如果当前子序列更长,则更新索引和长度。
  3. 输出结果:

    • 打印最大子序列的和、起始索引、结束索引以及实际的子序列。

示例与输出

对于示例列表 [1, 2, -5, 6, -3, -13434, 99, 99, -444, -7444, 100, 90, 8],该代码将输出:

sum( arr[10] .. arr[12] ) = 198
Subsequence: 100 90 8
登录后复制

注意事项

  • 空列表处理: 代码首先检查列表是否为空,如果为空,则输出 "empty array" 并退出。
  • 初始化: 正确初始化变量至关重要,尤其是 maxSumLength。
  • 时间复杂度: 该算法的时间复杂度为 O(n),因为它只需要一次遍历列表。

总结

本文提供了一个清晰的Java实现,用于在一个列表中找到元素和最大的最长连续子序列。 通过理解Kadane算法的变体,并结合长度判断,我们可以有效地解决这个问题。 提供的代码示例和解释可以帮助读者理解并应用该算法到实际场景中。 记住,在处理数组和子序列问题时,仔细考虑边界情况和初始化至关重要。

以上就是如何找出列表中元素和最大的最长连续子序列?的详细内容,更多请关注php中文网其它相关文章!

最佳 Windows 性能的顶级免费优化软件
最佳 Windows 性能的顶级免费优化软件

每个人都需要一台速度更快、更稳定的 PC。随着时间的推移,垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是,许多工具可以让 Windows 保持平稳运行。

下载
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
开源免费商场系统广告
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新 English
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号