首页 > 其他 > 详细

LintCode "Continuous Subarray Sum"

时间:2015-08-29 12:19:57      阅读:193      评论:0      收藏:0      [点我收藏+]

A variation to a classical DP: LCS.

技术分享
class Solution {
public:
    /**
    * @param A an integer array
    * @return  A list of integers includes the index of
    *          the first number and the index of the last number
    */
    vector<int> continuousSubarraySum(vector<int>& A) {
        vector<int> ret;

        size_t len = A.size();

        int curr = A[0];
        int sum = A[0], csum = A[0];
        int s = 0, e = 0, ss = 0, ee = 0;
        for (int i = 1; i < len; i++)
        {
            int nsum = csum + A[i];
            if (A[i] > nsum)
            {
                ss = ee = i;
                csum = A[i];
            }
            else
            {
                ee = i;
                csum = nsum;
            }
    
            if(csum > sum) // update global record
            {
                sum = nsum;
                s = ss;
                e = ee;
            }
        }

        ret.push_back(s);
        ret.push_back(e);
        return ret;
    }
};
View Code

LintCode "Continuous Subarray Sum"

原文:http://www.cnblogs.com/tonix/p/4768821.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!