目錄

?

1.題目描述

2.分析

3.代碼實(shí)現(xiàn)

---

1.題目描述

2.分析

此題的思路還是很簡(jiǎn)單的，做題的方法也有很多種，比如暴力解法，貪心算法解法，動(dòng)態(tài)規(guī)劃解法。

此處就講講貪心算法：

1.從數(shù)組0開始遍歷，更大值=MAX(更大值+當(dāng)前值，當(dāng)前值)
2.最大值=更大值中最大的值

貪心算法定義：貪心算法是指在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，只做出在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無(wú)后效性，即某個(gè)狀態(tài)以前的過(guò)程不會(huì)影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。

解題的一般步驟是：
1.建立數(shù)學(xué)模型來(lái)描述問(wèn)題；
2.把求解的問(wèn)題分成若干個(gè)子問(wèn)題；
3.對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解；
4.把子問(wèn)題的局部最優(yōu)解合成原來(lái)問(wèn)題的一個(gè)解。

3.代碼實(shí)現(xiàn)

int maxSubArray(int* nums, int numsSize){int MAX = nums[0], result = nums[0], sum = nums[0];for (int i = 1; i < numsSize; i++) {sum += nums[i];if (nums[i] <= sum ) {MAX = sum;} else {MAX = nums[i];sum = nums[i];}if (MAX >= result) {result = MAX;}}return result; }

總結(jié)

以上是生活随笔為你收集整理的最大子序和（Leetcode第53题)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。