wordpress 网站显示加载时长,个人主页搭建,阿里云做影视网站,图片点击切换网站模板题目 输入一个整型数组#xff0c;数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。 举例 输入#xff1a;2, -3, 4, 5, -9 输出#xff1a;9 和最大的连续子数组是 {4, 5}#xff0c;结果就是9。 思路… 题目 输入一个整型数组数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。 举例 输入2, -3, 4, 5, -9 输出9 和最大的连续子数组是 {4, 5}结果就是9。 思路 我们先假设和最大连续子数组是从第一个数开始的。初始化和为0。第一步是加上数字2此时和为2。第二步加上数字-3此时和为-1。那么问题来了我们到底要不要加上数字-3呢分析过程如下 加上-3。此时的和为-1然后由-1继续加下一个数。不加-3。也就是意味当前连续子数组就终结于-3之前的数字下一个连续子数组的和初始化为0再加上第一个数字-3和为-3。由上述分析可知加上-3此时累加的子数组和是-1不加-3此时累加的子数组和是-3。-1大于-3为了后续的累加和更大所以选择加上-3。 接下来第三步要不要加上数字4我们依据上面的决策流程继续分析。当加上数字4此时累加和为4-13不加上数字4意味着当前连续子数组终结于数字4之前此时的累加和初始化为0加上数字4后和等于4。显而易见4大于3所以我们选择抛弃前面的累加和由数字4继续开始。 后续步骤省略总结一番。当我们遍历数组时对于每个数字要么与前面的子数组累加要么作为新子数组的起点如果累加之后的子数组和小于或等于当前数字我们就选择抛弃前面的累加和将当前数字作为新子数组的起点。整个过程可以用表格总结如下 步骤操作累加的子数组和最大的子数组和1加2222加-3-123抛弃累加的和-1加4444加5995加-909代码 根据题目要求我们只需要求出连续子数组的最大和如果面试官还要求找到连续子数组的起点与终点下标那么最终的java代码如下 public class Main {public static int child_sum(int[] arr) {if (arr null || arr.length 1) {return 0;}int left0 0;int left1 0;int right 0;int max arr[0];int sum 0;for (int i 0; i arr.length; i) {sum arr[i];if (sum arr[i]) { //使用还是呢sum arr[i];left0 i;}if (sum max) {max sum;left1 left0;right i;}}System.out.println(left: left1 right: right max: max);return max;}public static void main(String[] args) {int[] arr1 new int[]{2, -3, 4, 5, -9};int[] arr2 new int[]{2, -2, 4, 5, -9};int[] arr3 new int[]{-2, -3, -4, -5, -9};child_sum(arr1);child_sum(arr2);child_sum(arr3);}
} 打印输出 left:2 right:3 max:9
left:2 right:3 max:9
left:0 right:0 max:-2 在上面的代码中使用小于等于或者使用小于有什么区别呢 假设数组为{2, -2, 4, 5, -9}如果判断条件是小于等于当前数字那么所得的最大连续子数组为{4, 5}。如果判断条件是小于当前数字那么所得的最大连续子数组为{-2, 2, 4, 5}。如果对最大连续子数组的长度没有明确要求使用小于等于进行判断即可。 转载于:https://www.cnblogs.com/yueshutong/p/11469200.html
