首页 > 其他 > 详细

LintCode "Minimum Subarray"

时间:2015-09-13 14:31:09      阅读:208      评论:0      收藏:0      [点我收藏+]

Typical solution: convert it to Maximum Array problem.

And here is my solution: O(n) by using Greedy strategy on this equation: sum[i..j] = sum[0..j] - sum[0..i-1].

class Solution {
public:
    /**
    * @param nums: a list of integers
    * @return: A integer denote the sum of minimum subarray
    */
    int minSubArray(vector<int> nums) 
    {
        auto len = nums.size();

        int ret = nums[0];
        vector<int> sums(len), maxs(len);
        sums[0] = nums[0];
        int cmax = max(0, nums[0]);
        
        for (int i = 1; i < len; i++)
        {
            //  calc sum
            sums[i] = nums[i] + sums[i - 1];
            //  calc prev max sum
            cmax = max(cmax, sums[i - 1]);
            maxs[i] = cmax;
            //
            ret = min(ret, sums[i] - maxs[i]);
        }

        return ret;
    }
};

LintCode "Minimum Subarray"

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

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