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

子数组的最大累加和问题

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

动态规划:

class Solution {
public:
    /**
     * max sum of the subarray
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxsumofSubarray(vector<int>& arr) {
        // write code here
        if (arr.size() == 0) return 0;
        vector<int> dp(arr.size(), 0);
        int maxsum = arr[0];
        dp[0] = arr[0];   // dp[i] 表示从arr[0]~arr[i]的最大累加和
        for (int i = 1; i < arr.size(); ++i) {
            dp[i] = max(arr[i], dp[i-1] + arr[i]);  // 递推公式
            maxsum = max(maxsum, dp[i]);
        }
        return maxsum;
    }
};
全部评论

相关推荐

完美的潜伏者许愿简历...:隐藏信息被你提取出来了,暗示,这就是暗示
点赞 评论 收藏
分享
06-17 21:57
门头沟学院 Java
白友:噗嗤,我发现有些人事就爱发这些,明明已读不回就行了,就是要恶心人
点赞 评论 收藏
分享
练习生懒羊羊:开飞机把这个公司创飞吧
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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