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.自己單幹

如果自己單幹比抱團還厲害，當然自己單幹咯