LeetCode第53题
Given an integer array nums, 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: 6Explanation: [4,-1,2,1] has the largest sum = 6.翻译：
给定一个整数组，找到相加之和最大的子数组，返回最大的和
思路1：
暴力循环不解释
1.循环遍历一个值的和，找出最大的那个
2.循环遍历两个相邻数的和，找出最大的那个
3.循环遍历三个相邻数的和，找出最大的那个
...
最后比较所有的最大和，得到最最大的那个
代码
class Solution { public int maxSubArray(int[] nums) { int sum = nums[0]; int length = nums.length; for(int i = 1;i<=length;i++){ int once = getOnce(nums,i); if(once>sum){ sum = once; } } return sum; } public int getOnce(int[] nums,int n){ int max = nums[0]; for(int i = 0;i<=(nums.length-n);i++){ int add = 0; int nn = n; while(--nn >= 0){ add+=nums[i+nn]; } if(add > max){ max = add; } } return max; }}跑起来没问题，但是提交后报错了！Time Limit Exceeded，就是运行超时了，因为循环了3遍，时间复杂度是N的3次方啊，所以抛弃
百度得到解决办法
思路2：
原数组 [-2,1,-3,4,-1,2,1,-5,4]
设置初始最大和为第一个数-2，从第二个数开始遍历
这里有一个思维技巧，就是只循环一遍，得到每个以当前值结尾的数组的最大值，一开始我没想明白这一块，后来多想几遍也就明白了
代码：
class Solution { public int maxSubArray(int[] nums) { int sum = nums[0]; int max = nums[0]; for (int i = 1; i < nums.length; i++) { System.out.print("当前值:"+nums[i]+"--当前值+前面的最大和:"+(sum + nums[i])); sum = Math.max(nums[i], sum + nums[i]); System.out.println("当前的最大和:"+sum); max = Math.max(max, sum); } return max; }}为何要这样比较呢，因为对于当前值来说，有两种可能
1.和前面的数组抱团
2.自己单干
如果自己单干比抱团还厉害，当然自己单干咯
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-05-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读