letecode [53] - Maximum Subarray

Given an integer arraynums, find the contiguous subarray(containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation:[4,-1,2,1] has the largest sum = 6.

题目大意：

　　给定数组，找到具有最大和的连续子数组，返回该最大和。

理解：

　　初始最大和max、临时数值sum和为nums[0]。

　　当sum<0 时，若下一个数nums[i] 大于sum，则sum重新设置为nums[i]。

　　当sum>0时，直接加上下一个数nums[i]。

　　每次都需将sum与最大和max比较，更新max值。

代码 C++：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n==0) return 0;
        int max = nums[0],sum=nums[0] ,i;
        for(i=1;i<n;++i){
　　　　　　　 
            if(sum<0 && sum<nums[i]){
                sum = nums[i];
                if(max<sum) max = sum;
                continue;
            }
            sum = sum + nums[i];
            if(max<sum) max = sum;
        }
        if(max<sum) max = sum;
        return max;
    }
};

运行结果：

　　执行用时 : 12ms　　内存消耗 :9.4 MB 优质内容筛选与推荐>>
1、C语言I作业09
2、Window Or Liunx下载并且使用Android SDK源码的最简单方法
3、第五章《jQuery事件处理》
4、hdu1078 FatMouse and Cheese(记忆化搜索)
5、erlang连接mysql [转]

0 │ 收藏 │ 举报

朋友将在看一看看到

分享想法到看一看