输入一个单链表,链表中一个或多个连续的整数组成一个子链表。求所有子链表和的最大值。
1.你能不使用额外的O(n)空间复杂度来完成该题吗?
2.你能使用递归解法来完成该题吗?
3.如果你能使用递归解法完成本题,本题也可以看成二叉树中的最大路径和的一个子问题,可以尝试递归解法该题之后,去突破二叉树中的最大路径和
数据范围:链表长度满足 ,链表中的值满足
{1,-2,3,10,-4,7,2,-5}
18
{2}
2
{-10}
-10
public int FindGreatestSumOfSubArray (ListNode head) { int max = 0; int sum = 0; while(head != null) { sum += head.val; if (sum < 0) { sum = 0; } if (sum > max) { max = sum; } head = head.next; } return max; }
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; } };