连续子链表最大和

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