输入一个单链表，链表中一个或多个连续的整数组成一个子链表。求所有子链表和的最大值。
1.你能不使用额外的O(n)空间复杂度来完成该题吗？
2.你能使用递归解法来完成该题吗？
3.如果你能使用递归解法完成本题，本题也可以看成二叉树中的最大路径和的一个子问题，可以尝试递归解法该题之后，去突破二叉树中的最大路径和
数据范围：链表长度满足 
，链表中的值满足 
[编程题]连续子链表最大和
连续子链表的最大和
思路：
1.由于需要求最长的连续子串之和，所以先可以初始化为最小值
2.用动态规划的解决连续的最长的子串和的思想
3.用一个个max1记录两种选择中较大值：一种情况是将当前的数加到原先串的后面，另一种情况是将该数直接作为一个新的串的起始点
4.再与之前记录下来的最大的连续子串
展开全文
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/*
展开全文
动态规划（C++）
这里想法还是比较简单的，和上一题基本无异，只是将数组变成了链表，动态规划比较重要的就是可查询的历史值，减少代码复用。
连续子数组最大和（上一题）
https://www.nowcoder.com/practice/1718131e719746e9a56fb29c40cc8f95
展开全文
和之前求子数组的最大和一样的思路。
把当前链表和nowsum和所求链表和的最大值maxsum均设为第一个元素值，
然后从第二个元素值往后遍历，如果当前和小于0，那么就舍弃前面的求和，把当前值作为第一个元素开始求和，
如果当前和不小于0，那么就把当前值加入成为新的数组和，
再与
展开全文
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
*
展开全文
利用动态规划的思想，最大子链表的和只与之前子链表+当前值 和 当前值有关，并用一个全局值记录整个过程中出现的最大值
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next =
展开全文
package main
import . "nc_tools"
/*
* type ListNode struct{
* Val int
* Next *ListNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
展开全文
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
*
展开全文
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListN
展开全文
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
