连续子链表最大和

int FindGreatestSumOfSubArray(ListNode* head) {
        // write code here
        int res =head->val;
        int presum =0;
        while(head){
            presum =max(presum+head->val,head->val);
            res =max(res,presum);
            head =head->next;
        }
        return res;

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
}

		// 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;

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;
    }
}

int FindGreatestSumOfSubArray(ListNode* head) {
        vector<int>nums;
        while(head){
            nums.push_back(head->val);
            head=head->next;
        }
        vector<int>dp(nums.size());
        int ans=dp[0]=nums[0];
        for(int i=1;i<nums.size();i++){
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
            ans=max(ans,dp[i]);
        }
        return ans;
    }

static const auto io_sync_off = []() {
    std::ios::sync_with_stdio(false);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
    return nullptr;
}
();
class Solution {
  public:
    int FindGreatestSumOfSubArray(ListNode* head) {
        int a = head->val, b = INT_MIN;
        while (head) {
            b = max(head->val, b + head->val);
            a = max(a, b);
            head = head->next;
        }
        return a;
    }
};