题解 | #连续子链表最大和#
连续子链表最大和
http://www.nowcoder.com/practice/650b68dfa69d492d92645aecd7da9b21
和之前求子数组的最大和一样的思路。
把当前链表和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;
}
投递大连飞创信息技术有限公司等公司10个岗位
