个人网站建设 优帮云,wordpress采集视频插件,无锡网站网页设计,wordpress 怎么安装主题输入一个 非空 整型数组#xff0c;数组里的数可能为正#xff0c;也可能为负。 数组中一个或连续的多个整数组成一个子数组。 求所有子数组的和的最大值。 要求时间复杂度为 O(n)。 数据范围#xff1a; 数组长度 [1,1000]。 数组内元素取值范围 [−200,200][−200,200]。 … 输入一个 非空 整型数组数组里的数可能为正也可能为负。 数组中一个或连续的多个整数组成一个子数组。 求所有子数组的和的最大值。 要求时间复杂度为 O(n)。 数据范围 数组长度 [1,1000]。 数组内元素取值范围 [−200,200][−200,200]。 样例
输入 [ 1-2310-472-5] 输出 18 解题思路 本题是求子数组的最大值。
对于数组 [1......x......... 2]。用 变量s 记录 x 前一个子数组的值若 s 0 , x s, 反而比 x 本身小那么不如从 x 开始重新设立一个新的子数组。对于 s 0 , s x 一定要比 x 大所以不如将 x 纳入 子数组 s 内 不必担心 x 小于0使新子数组值变小因为res变量时刻在更新最大值。对于 s 0 的情况完全可以归纳到 s 0 内。
理论成立代码如下
class Solution {public int maxSubArray(int[] nums) {int res -201;int s 0;for(int x : nums){if(s 0)s 0;s s x;res Math.max(res,s);}return res;}
}
