题解 | #跳台阶扩展问题#

连续子链表最大和

http://www.nowcoder.com/practice/650b68dfa69d492d92645aecd7da9b21

解法一,动态规划解决

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
int num[100000] = {0};
class Solution {
public:
    int FindGreatestSumOfSubArray(ListNode* head) {
        int n,i = 0;
        while(head != NULL){
            num[i++] = head->val;
            head = head->next;
        }
        n = i;
        long int MAX = num[0],sum = num[0];
        for (int i = 1; i < n; ++i) {
            if (sum < 0 && sum < num[i])
                sum = num[i];
            else
                sum += num[i];
            MAX = max(MAX, sum);
        }
        return MAX;
    }
};

解法二,递归解决,后面补充

全部评论

相关推荐

测试糕手手:社会第一课,随便吹牛逼,直接说四个月,别老实。老实人只会被欺负
点赞 评论 收藏
分享
见见123:简历没有啥问题,是这个社会有问题。因为你刚毕业,没有工作经历,现在企业都不要没有工作经历的。社会病了。
点赞 评论 收藏
分享
头顶尖尖的程序员:我是26届的不太懂,25届不应该是找的正式工作吗?为什么还在找实习?大四还实习的话是为了能转正的的岗位吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务