看黄色视频在线进,美女免费一级操逼视频,免费黄v在线播放,午夜无码电影,三级草逼,蜜芽AV久久,国产对白国语对白,日韩视频五区

算法的重要性，我就不多說了吧，想去大廠，就必須要經(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)鍵與解決問題的核心最小點(diǎn)”這個思維的關(guān)鍵。

1、暴力解法：

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

private?int?max = Integer.MIN_VALUE;
????public?int?maxSubArray(int[] nums)?{
????????int?sum;
????????for?(int?i = 0; i < nums.length; i++) {// 子序列左端點(diǎn)
????????????for?(int?j = i; j < nums.length; j++) {// 子序列右端點(diǎn)
????????????????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ù)組實(shí)際上，要么是以第i-1個元素結(jié)尾且和最大的連續(xù)子數(shù)組加上這個元素，要么是只包含第i個元素，即sum[i]= max(sum[i-1] + a[i], a[i])。

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

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

本題還有其他解法，比如官方還提供了分治算法，大家有興趣的可以了解一下。

好了，今天的文章就到這里，如果覺得有所收獲，請順手點(diǎn)個在看或者轉(zhuǎn)發(fā)吧，你們的支持是我最大的動力。

上期推文：

LeetCode1-50題匯總，速度收藏！

LeetCode刷題實(shí)戰(zhàn)51：N 皇后

LeetCode刷題實(shí)戰(zhàn)52：N皇后 II

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

題意

樣例

解題