首页 > 试题广场 >

连续子链表最大和

[编程题]连续子链表最大和

输入一个单链表，链表中一个或多个连续的整数组成一个子链表。求所有子链表和的最大值。

1.你能不使用额外的O(n)空间复杂度来完成该题吗？

2.你能使用递归解法来完成该题吗？

3.如果你能使用递归解法完成本题，本题也可以看成二叉树中的最大路径和的一个子问题，可以尝试递归解法该题之后，去突破二叉树中的最大路径和

数据范围：链表长度满足 $1 \le n \le 10^5 \$ ，链表中的值满足 $|val| \le 10000 \$

示例1

输入

{1,-2,3,10,-4,7,2,-5}

示例2

{2}

示例3

{-10}

-10

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

动态规划记忆化搜索链表

难度：

0条回答 25收藏 4435浏览

查看代码

连续子链表最大和

扫一扫，把题目装进口袋