题解 | #连续子数组的最大和(二)#

连续子数组的最大和(二)

http://www.nowcoder.com/practice/11662ff51a714bbd8de809a89c481e21

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindGreatestSumOfSubArray(vector<int>& array) {
        // write code here
        int res=array[0], res_start=0, res_len=1;
        int cur_start=0, cur_len=1;
        int n = array.size();
        
        vector<int> dp(n, 0);
        dp[0] = array[0];
        
        for(int i=1; i<n; i++){
            dp[i] = max(dp[i-1]+array[i], array[i]);
            if(dp[i-1]+array[i] < array[i]){
                cur_start = i;
                cur_len = 1;
            }
            else{
                cur_len += 1;
            }
            if(res < dp[i]){
                res = dp[i];
                res_start = cur_start;
                res_len = cur_len;
            }
            else if(res == dp[i]){
                if(cur_len > res_len){
                    res_len = cur_len;
                    res_start = cur_start;
                }
            }
        }
        
        vector<int> out;
        for(int i=res_start; i<res_start+res_len; i++){
            out.push_back(array[i]);
        }
        return out;
    }
};
全部评论

相关推荐

昨天 15:52
东南大学 C++
点赞 评论 收藏
分享
白火同学:大二有这水平很牛了,可以适当对关键信息加粗一点,比如关键技术、性能指标之类的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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