在线学做衣服 的网站,网页版qq在线登录,百度手机助手安卓版,谷歌广告代运营题目描述#xff1a;
给你一个整数数组 nums #xff0c;请你找出一个具有最大和的连续子数组#xff08;子数组最少包含一个元素#xff09;#xff0c;返回其最大和。
子数组 是数组中的一个连续部分。 示例 1#xff1a;
输入#xff1a;nums [-2,1,-3,4,-1,2,1,…题目描述
给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
子数组 是数组中的一个连续部分。 示例 1
输入nums [-2,1,-3,4,-1,2,1,-5,4]
输出6
解释连续子数组 [4,-1,2,1] 的和最大为 6 。示例 2
输入nums [1]
输出1示例 3
输入nums [5,4,-1,7,8]
输出23提示
1 nums.length 105-104 nums[i] 104 进阶如果你已经实现复杂度为 O(n) 的解法尝试使用更为精妙的 分治法 求解。
通过次数
1.5M
提交次数
2.8M
通过率
54.9%
思路和题解在线处理)
当一个子列的和sum加上后一项a[i]时只有当sum0时后一项加上sum才能增大才有扩大子列的可能。当sum小于零时至少它不会将包含后一项a[i]的子序列的和增大所以我们就直接舍弃。先让max设置为nums[i]的最小值-10^4sum的初值为零。遍历一次nums数组每次summus[i]如果sum0,就令sum0如果summax就令maxsum。最后返回sum。
代码
class Solution {
public:int maxSubArray(vectorint nums) {int sum0;int max-10009;for(int i0;inums.size();i){sumnums[i];if(summax){maxsum;}if(sum0){sum0;}}return max;}
};
