查找数组中和最大的连续子序列,并优先选择最长的子序列

风涛大大_3374

风涛大大_3374

2025-10-29

888人浏览

原创

查找数组中和最大的连续子序列,并优先选择最长的子序列

本文旨在提供一种在给定整数列表中查找和最大的连续子序列,并优先选择最长子序列的解决方案。通过Kadane算法的变体,我们不仅找到最大和,还能在存在多个最大和子序列时,确定长度最长的那个。本文将详细解释算法原理,并提供Java代码示例,帮助读者理解和应用该方法。

问题描述

给定一个整数列表,我们需要找到一个连续的子序列,使得该子序列的元素之和最大。如果存在多个具有相同最大和的子序列,则选择长度最长的那个子序列。

解决方案:Kadane算法的扩展

经典的Kadane算法用于查找数组中和最大的连续子数组。为了满足“优先选择最长子序列”的要求,我们需要对Kadane算法进行一些修改。

核心思想是,在更新最大和子序列时,不仅要比较当前子序列的和与已知的最大和,还要比较它们的长度。如果当前子序列的和与最大和相等,则选择长度更长的子序列。

Java调试
Java调试

通过 JDWP 实现 Java 远程调试:连接远程 JVM、设置断点、单步执行代码、查看变量值、获取调用栈。适用于需要调试远程 Java 应用、排查运行时状态、追踪代码执行流程的场景。 术语注解 JDWP:Java Debug Wire Protocol,Java 调试有线协议(Java 远程调试底层通信协议) remote JVM:远程 Java 虚拟机 step through code:代码单步调试(步入 / 步过 / 步出调试) inspect variables:变量查看 / 变量检视 stac

下载

Java 代码实现

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

public class MaxSubsequence {

    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  maxSum) {
                maxSumStartIndex = lastSumStartIndex;
                maxSumLastIndex = i;
                maxSumLength = currentLength;
                maxSum = lastSum;
            } else if (lastSum == maxSum && currentLength > maxSumLength) {
                // 如果当前子序列的和等于最大和,但长度更长,则更新最大和子序列
                maxSumStartIndex = lastSumStartIndex;
                maxSumLastIndex = i;
                maxSumLength = currentLength;
            }
        }

        System.out.println("sum( arr[" + maxSumStartIndex + "] .. arr[" + maxSumLastIndex + "] ) = " + maxSum);
        System.out.print("Subsequence: ");
        for (int i = maxSumStartIndex; i <p><strong>代码解释:</strong></p>
<ol>
<li>
<strong>初始化:</strong> maxSumStartIndex、maxSumLastIndex、maxSum 和 maxSumLength 用于跟踪和最大的子序列的起始索引、结束索引、和以及长度。lastSumStartIndex 和 lastSum 用于跟踪当前子序列的起始索引和和。</li>
<li>
<strong>循环遍历:</strong> 遍历列表中的每个元素。</li>
<li>
<strong>更新当前子序列:</strong> 如果当前元素大于当前子序列的和,则从当前元素开始一个新的子序列。否则,将当前元素添加到当前子序列的和中。</li>
<li>
<strong>更新最大和子序列:</strong><ul>
<li>如果当前子序列的和大于最大和,则更新最大和子序列的起始索引、结束索引、长度和和。</li>
<li>如果当前子序列的和等于最大和,但长度更长,则更新最大和子序列的起始索引、结束索引和长度。</li>
</ul>
</li>
<li>
<strong>输出结果:</strong> 打印最大和子序列的和以及子序列本身。</li>
</ol>
<h3>注意事项</h3>
<ul>
<li>
<strong>空列表处理:</strong> 代码中包含了对空列表的检查,以避免空指针异常。</li>
<li>
<strong>负数处理:</strong> 该算法能够正确处理包含负数的列表。</li>
<li>
<strong>整数溢出:</strong> 如果列表中的数字很大,需要注意整数溢出的问题。可以考虑使用 long 类型来存储和。</li>
</ul>
<h3>总结</h3>
<p>通过对Kadane算法进行简单的修改,我们能够找到给定整数列表中和最大的连续子序列,并在存在多个最大和子序列时,优先选择长度最长的那个。该算法的时间复杂度为 O(n),其中 n 是列表的长度。  这个方法提供了一个有效的解决方案,在实际应用中具有一定的价值。</p></integer>

相关专题

更多
C++ 智能指针与现代内存管理
C++ 智能指针与现代内存管理

深入讲解 C++ 现代内存管理的核心工具——智能指针,涵盖 unique_ptr 独占所有权语义、shared_ptr 引用计数机制与循环引用问题、weak_ptr 弱引用的应用场景、make_unique/make_shared 工厂函数的性能优势、自定义删除器的编写、RAII 资源管理思想的实践,以及从裸指针迁移到智能指针的重构策略,帮助开发者编写安全无泄漏的现代 C++ 代码。

2026.04.23

399

31

空指针异常处理
空指针异常处理

本专题整合了空指针异常解决方法,阅读专题下面的文章了解更多详细内容。

2025.11.16

179

10

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7216

4

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

140

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

80

15

Postman身份认证怎么配置
Postman身份认证怎么配置

本专题从实际API接口调试场景出发,讲解Postman身份认证的完整配置流程,包括常见认证协议介绍、授权参数设置、访问令牌填写、OAuth 2.0授权及认证失败排查,帮助用户正确完成接口授权与访问验证。

2026.11.06

160

12

Postman请求头Headers怎么设置
Postman请求头Headers怎么设置

围绕Postman HTTP请求头配置展开,讲解Headers选项的具体使用方式,包括Key和Value参数填写、请求头信息添加、常见Header字段设置及请求头修改方法,帮助用户解决接口调试过程中遇到的请求头配置问题。

2026.11.06

140

13

Postman接口请求发送教程
Postman接口请求发送教程

详细介绍Postman接口请求的创建与发送方法,涵盖GET和POST请求、URL配置、请求参数、Headers请求头、Body请求体设置以及响应结果查看,帮助用户掌握Postman接口请求的完整操作流程。

2026.11.06

120

10

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
dev.java 官方:Learn Java
dev.java 官方:Learn Java

共0课时 | 0人学习

Java JDBC数据库连接官方教程
Java JDBC数据库连接官方教程

共0课时 | 0人学习