LeetCode第53题

• 2019 年 10 月 7 日
• 筆記

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.自己单干

如果自己单干比抱团还厉害，当然自己单干咯