題目鏈接
法一：枚舉
雙重for循環(huán)暴力枚舉
時間復雜度：O(n^2)

法二：動態(tài)規(guī)劃
時間復雜度：O(n)
1、構(gòu)建狀態(tài)轉(zhuǎn)移方程
假設以nums數(shù)組中第i個位置結(jié)尾的最大子序和為P(i)
那么以i+1位置結(jié)尾的最大子序和就只有兩種選擇P(i)+nums[i+1]、nums[i+1]。
2、當Pi>0時，P(i+1)=P(i)+nums[i+1]，否則P(i+1)=nums[i+1]，并設一個變量Max隨著循環(huán)記錄更大的P值，最后返回。
3、由于第0個位置前面沒有P(-1)，所以P與Max的初始值需手動設置，并且從數(shù)組的第二個值開始遍歷。

C代碼

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

Java代碼

class Solution {public int maxSubArray(int[] nums) {int P=nums[0],Max=P,numsSize=nums.length;for(int i=1;i<numsSize;i++){if(P>0) P=P+nums[i];else P=nums[i];if(P>Max) Max=P;}return Max;} }

補充：不使用max函數(shù)是因為此處調(diào)用函數(shù)的時間效率沒有if-else高。

總結(jié)

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

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