题解 | #子数组的最大累加和问题#

子数组的最大累加和问题

http://www.nowcoder.com/practice/554aa508dd5d4fefbf0f86e5fe953abd

遍历数组统计累加和,如果累加和小于0则统计后面的数时会导致亏损,还不如不加,不加就是将累加和置0。最大的累加和就是答案,用一个变量来记录。

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        // write code here
        int max_sum = 0;
        //遍历数组统计累加和,如果累加和小于0则统计后面的数时会导致亏损
        //此时应该将累加和置0;
        int curr_sum = 0;
        for(auto& v: arr)
        {
            curr_sum += v;
            curr_sum = max(curr_sum,0);
            max_sum  = max(max_sum, curr_sum);
        }

        return max_sum;
    }
};
全部评论

相关推荐

昨天 11:08
门头沟学院 Java
投递京东等公司9个岗位
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 13:54
点赞 评论 收藏
分享
仁者伍敌:难怪小公司那么挑剔,让你们这些大佬把位置拿了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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