成人美女视频网站,污美女视频下载

?LeetCode刷題實戰(zhàn)53：最大子序和

2021.01.16

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做 最大子序和，我們先來看題面：

https://leetcode-cn.com/problems/maximum-subarray/

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

題意

給定一個整數(shù)數(shù)組 nums ，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素），返回其最大和。

樣例

輸入: [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。

解題

本題為非常經(jīng)典的一道算法入門題，有著多種非常高效的解題方法，可以幫助答題感受到“找到問題的關(guān)鍵與解決問題的核心最小點”這個思維的關(guān)鍵。

1、暴力解法：

題目要求是找出最大子序和，那么我們就把所有的子序都找出來，并且出每個子序的和然后找到最大的一個就可以了。題目已給一個序列，我們需要做的就是確定所有能找到的開始序號與結(jié)束序號，然后把這個序號中的所有子序和都求出來。具體實現(xiàn)如下：

private int max = Integer.MIN_VALUE;
    public int maxSubArray(int[] nums) {
        int sum;
        for (int i = 0; i < nums.length; i++) {// 子序列左端點
            for (int j = i; j < nums.length; j++) {// 子序列右端點
                sum = 0;
                for (int k = i; k <= j; k++) {//暴力計算
                    sum += nums[k];
                }
                if (sum > max) {
                    max = sum;
                }
            }
        }
        return max;
    }

2、動態(tài)規(guī)劃解法：

設(shè)sum[i]為以第i個元素結(jié)尾且和最大的連續(xù)子數(shù)組。假設(shè)對于元素i，所有以它前面的元素結(jié)尾的子數(shù)組的長度都已經(jīng)求得，那么以第i個元素結(jié)尾且和最大的連續(xù)子數(shù)組實際上，要么是以第i-1個元素結(jié)尾且和最大的連續(xù)子數(shù)組加上這個元素，要么是只包含第i個元素，即sum[i]= max(sum[i-1] + a[i], a[i])。

可以通過判斷sum[i-1] + a[i]是否大于a[i]來做選擇，而這實際上等價于判斷sum[i-1]是否大于0。由于每次運算只需要前一次的結(jié)果，因此并不需要像普通的動態(tài)規(guī)劃那樣保留之前所有的計算結(jié)果，只需要保留上一次的即可，因此算法的時間和空間復雜度都很小。

class Solution {
    public int maxSubArray(int[] nums) {// 動態(tài)規(guī)劃法
        int sum=nums[0];
        int n=nums[0];
        for(int i=1;i<nums.length;i++) {
            if(n>0)n+=nums[i];
            else n=nums[i];
            if(sum<n)sum=n;
        }
        return sum;
    }
}