leetcode53 Maximum Subarray 最大連續子數組

Bamboy 發布于2019-08-14 18:08 / 1700人閱讀

摘要：我們可以分別得出這三種情況下的最大子數列和，并比較得出最大的那個。我們只需要考慮左子列的最大和以及跨越了左右的中子列的最大值。

題目要求

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

即：尋找數列中的一個子數列，該數列中的值得和是所有子數列中最大的。

思路一：divide&conquer

我們可以從數列的中間節點將數列分為兩個子數列，則最大的子數列要么在左子列，要么在右子列，要么跨越了左子列和右子列。我們可以分別得出這三種情況下的最大子數列和，并比較得出最大的那個。
divide&conquer即遞歸思路，將復雜問題分解為簡單的小問題分別解決。遞歸的重點在于覆蓋所有可能情況，并且覆蓋到基類。

    public int maxSubArray(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        return maxSubArray(nums, start, end);
        
        
    }
    
    //遞歸調用該方法
    public int maxSubArray(int[] nums, int start, int end){
        if(start==end){
            return nums[start];
        }
        int mid = (start + end) / 2;
        //獲得最大左子列
        int leftMax = maxSubArray(nums, start, mid);
        //獲得最大右子列
        int rightMax = maxSubArray(nums, mid+1, end);
        
        //獲得最大中子列
        int leftSumMax = Integer.MIN_VALUE;
        int temp = 0;
        do{
            temp += nums[mid];
            if(temp>leftSumMax){
                leftSumMax = temp;
            }
        }while((--mid)>=start);
        
        temp = 0;
        mid = (start + end)/2 + 1;
        int rightSumMax = Integer.MIN_VALUE;
        do{
            temp += nums[mid];
            if(temp>rightSumMax){
                rightSumMax = temp;
            }
        }while((++mid)<=end);
        int midMax = leftSumMax + rightSumMax;
        return Math.max(Math.max(leftMax, rightMax), midMax);
    }

思路二：divide&conquer2 recursion

上面是將數組從中劃分為兩個子數組,這里我們還可以劃分為nums[n-1]和nums[n]。這樣我們就可以將右子列的情況簡化為直接返回右子列的值。我們只需要考慮左子列的最大和以及跨越了左右的中子列的最大值。所以我們需要記錄兩個值，第一個是當前最大和，還有一個是到nums[n-1]的最大子列和。

    public int maxSubArray(int[] A) {
        int n = A.length;
        //存儲經過下標為i的最大子數列和，用于判斷中子列
        int[] dp = new int[n];
        dp[0] = A[0];
        int max = dp[0];
        
        for(int i = 1; i < n; i++){
            dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
            max = Math.max(max, dp[i]);
        }
        return max;    
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器最大連續子串算法數組連續判斷最大子序列算法最大子數列

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/67022.html

leetcode_53 Maximum Subarray

摘要：如果單開元素加和更大判斷前面的子數組和是不是小于。此元素就成為了子數組的第一個元素。每次操作都要判斷，當前是否是最大值，更新值。題目詳情 Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given t...

y1chuan 2019-08-15 13:37 評論0 收藏0
動態規劃法（八）最大子數組問題（maximum subarray problem）

摘要：動態規劃法用表示最大子數組的結束下標為的情形，則對于，有這樣就有了一個子結構，對于初始情形，遍歷就能得到這個數組，其最大者即可最大子數組的和。動態規劃法想法巧妙，運行效率也高，但是沒有普遍的適用性。問題簡介 ??本文將介紹計算機算法中的經典問題——最大子數組問題（maximum subarray problem）。所謂的最大子數組問題，指的是：給定一個數組A，尋找A的和最大的非空連續...

jzman 2019-07-30 16:46 評論0 收藏0
[Leetcode] Maximum Subarray 子序列最大和

摘要：最新更新請見原題鏈接動態規劃復雜度時間空間思路這是一道非常典型的動態規劃題，為了求整個字符串最大的子序列和，我們將先求較小的字符串的最大子序列和。而最大子序列和的算法和上個解法還是一樣的。 Maximum Subarray 最新更新請見：https://yanjia.me/zh/2019/02/... Find the contiguous subarray within an ar...

summerpxy 2019-08-14 16:11 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
leetcode152 Maximum Product Subarray

摘要：題目要求從一個整數數組中找到一個子數組，該子數組中的所有元素的乘積最大。比如數組的最大乘積子數組為思路與代碼這題目考察了動態編程的思想。至于為什么還要比較，是因為如果是一個負數的，那么之前的最小乘積在這里可能就成為了最大的乘積了。題目要求 Find the contiguous subarray within an array (containing at least one num...

Arno 2019-08-16 10:57 評論0 收藏0