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

子数组的最大累加和问题

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;
    }
};
全部评论

相关推荐

合不合适,我自己说了才算
码农索隆:hr:“真执着啊,来我公司当法人吧”
点赞 评论 收藏
分享
06-08 22:25
门头沟学院 Java
从零开始的转码生活:这hr不会打开手机不分青红皂白给所有人群发这句话,过一会再给所有人再发一遍,这肯定会有重复的,不管,再过一会再发一遍
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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