和之前求子数组的最大和一样的思路。
把当前链表和nowsum和所求链表和的最大值maxsum均设为第一个元素值,
然后从第二个元素值往后遍历,如果当前和小于0,那么就舍弃前面的求和,把当前值作为第一个元素开始求和,
如果当前和不小于0,那么就把当前值加入成为新的数组和,
再与最大数组和比较,并更新
int FindGreatestSumOfSubArray(struct ListNode* head ) { if(head == NULL) return 0; struct ListNode* p = head; int nowsum = p->val, maxsum = p->val; while(p->next != NULL){ //从头结点后面结点开始的 if(nowsum < 0) nowsum = p->next->val; //舍弃前面数组和,从当前再开始求和 else nowsum += p->next->val; //把当前值并入数组和 if(maxsum < nowsum) maxsum = nowsum; //比较,更新 p = p->next; //指针后移直到倒数第二个结点,最后一个结点不会进入while循环 } return maxsum; }