连续子链表最大和

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

热度指数：1403 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

小谷围做题家

package main
import _"fmt"
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return int整型
*/
func FindGreatestSumOfSubArray( head *ListNode ) int {
    sum,max:=head.Val,head.Val
    for p:=head.Next;p!=nil;p=p.Next{
        if sum+p.Val<=p.Val{
            sum=p.Val
        }else{
            sum+=p.Val
        }
        if sum>max{
            max=sum
        }
    }
    return max
}

发表于 2023-03-09 08:09:30 回复(0)