Leetcode — 53. Maximum Subarray (中文)

問題連結: https://leetcode.com/problems/maximum-subarray/

題目給一整數陣列nums, 求陣列中連續位置數字的最大總和

範例 
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
因為 [4,-1,2,1] 總和為6

想法:

所以題目的意思就是要我們找到有最大總和的"目標陣列"。
最直白的方法就是用暴力解, 拿兩個pointer i跟j, 來當作連續位置的的起點跟終點位置
程式碼如下 —

public int maxSubArray(int[] nums) {
        int n = nums.length; 
        int max = nums[0];
        for(int i=0;i<n;i++)
        {
            int temp = 0;
            for(int j=i;j<n;j++)
            {
                temp += nums[j];
                max = Math.max(max,temp);
            }
        }
        return max;
    }

整個程式的時間複雜度為O(n²) 因為我們把每個組合起點終點都試過一遍
也因為如此, 程式碼需要183ms 才能跑完, 只贏過5%的人

那我們來想, 有沒有辦法用O(n)來找到答案? 💭

因為我們發現 上述的程式碼, 很有可能一直浪費時間在累加著 我們早已知道不可能為答案的"目標陣列"總和, 或者是在位置i時 重複動作我們在i-1時就加過的陣列總和
如果不用兩個loop來跑, 我們需要一個變數temp來控制到位置i時可得到的最大總和

• 當temp總和是負數的時候 我們果斷放棄現在加總的全部,
  原因是因為就算nums[i]也是負數, 負數加負數也是越來越小; 但如果nums[i]是正的, nums[i]反而會被前面累加的負數總和拖累, 因此放棄過去比較好
• 而如果前面累積總和的是正的, 就果斷的把nums[i]加上去
  就算nums[i]是負數拖累也沒關係, 因為i後面的數字還有機會可以讓我們"目前陣列"累加到更高的總和

public int maxSubArray(int[] nums) {
        int n = nums.length; 
        int max = nums[0];
        int temp = nums[0];
        for(int i=1;i<n;i++)
        {
            if(temp<0)
                temp = nums[i];
            else
                temp += nums[i];
            max = Math.max(max,temp);
        }
        return max;
    }

加碼

雖然我們已成功找到O(n)解法, 但題目有一個follow up的挑戰我們是否可以用divide and conquer來解這題 (時間複雜度為O(nlgn))

若想要用divide and conquer, 代表我們會把問題切小,並且切到不能再切,
再回傳我們指定的起點i與終點j的陣列位置中 最大的總和
最大總和的陣列組合方式有三種:
1. 前半 — 也就是起點i到中間點mid前之間的最大總和
2. 後半 — 中間點mid後到終點j之間的最大總和
3. 中間 — 一定包含中點mid, 並且從mid中間兩側延伸的最大總和

public int maxSubArray(int[] nums) {
        return helper(nums,0,nums.length-1);
    }
    public int helper(int[] nums,int i,int j){
        if(i==j)
            return nums[i];
        if(i>j)
            return Integer.MIN_VALUE;
        int mid= i+(j-i)/2;
        int leftSum = helper(nums,i,mid-1);
        int rightSum = helper(nums,mid+1,j);
        
        int crossSum = nums[mid]; 
        //from mid to left
        int tempLeft = 0;
        int maxLeft = 0;
        for(int k=mid-1;k>=i;k--)
        {
            tempLeft += nums[k];
            maxLeft = Math.max(maxLeft,tempLeft);
        }
        //from mid to right
        int tempRight = 0;
        int maxRight = 0;
        for(int k=mid+1;k<=j;k++)
        {
            tempRight += nums[k];
            maxRight = Math.max(maxRight,tempRight);
        }
        crossSum += maxLeft+maxRight;
        
        return Math.max(crossSum, Math.max(leftSum,rightSum));
    }