连续子链表最大和

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

热度指数：1413 时间限制：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，点此查看相关信息

算法知识视频讲解

Java

BlueProtocol

		// write code here
		if (head.next == null) {
			return head.val;
		}
		ArrayList<Integer> integerArrayList = new ArrayList<Integer>();
		while (head != null) {
			integerArrayList.add(head.val);
			head = head.next;
		}
		int[] headIntArray = integerArrayList.stream().mapToInt(Integer::intValue).toArray();
        int len = headIntArray.length;
        int[] dp = new int[len];
        int max = headIntArray[0];
        dp[0] = headIntArray[0];
        for (int i = 1; i < len; i++) {
            dp[i] = Math.max(dp[i-1]+headIntArray[i],headIntArray[i]);
            max = Math.max(dp[i],max);
        }
        return max;

发表于 2022-08-10 23:06:57 回复(0)

Java

爱睡觉的杨大爷

import java.util.*;
public class Solution {
  
    public int FindGreatestSumOfSubArray (ListNode head) {
        // 使用动态规划的思想，达到时间复杂度O(n),空间复杂度O(1)
        //遍历到每一个节点，就记录下当前节点的最大子链表和，遍历到末尾，返回就行
        //这里是链表，事先不知道长度，所以要创建dp[] 数组还得先遍历一次链表，所以‘
        //这里只用两个个变量，一个pre代表dp[i] ,一个max记录最大和，
        //递推方程： dp[i]=Math.max(nums[i],dp[i-1]+nums[i]); 
        if(head.next==null)return head.val;
        int max=0;
        int pre=0;
        while(head!=null){
            pre=Math.max(head.val,pre+head.val);
            max=Math.max(max,pre);
            head=head.next;
        }
        return max;
    }
}

发表于 2022-07-30 12:06:24 回复(0)

Java

王②虎

与连续子数组的最大和方法一致

    public int FindGreatestSumOfSubArray (ListNode head) {
        int ret = head.val, pre = 0;
        while (head != null) {
            pre = Math.max(pre + head.val, head.val);
            ret = Math.max(ret, pre);
            head = head.next;
        }
        return ret;
    }

发表于 2022-02-09 12:04:02 回复(0)