來源：https://leetcode.com/problems/maximum-subarray

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.

遍歷（時間復雜度高）

若全負，取最大元素

否則比較以每個元素作為開頭（或結尾）的所有連續子數組的和

Python

class Solution:def FindGreatestSumOfSubArray(self, array):if max(array) < 0:return max(array)max_sum = 0cur_sum = 0for i in range(len(array)):cur_sum = 0for j in range(i, len(array)):cur_sum += array[j]max_sum = max(cur_sum, max_sum)return max_sum

動態規劃

遍歷一次，計算以當前元素結尾的連續子數組和的最大值：

若以前一個元素結尾的連續子數組和的最大值為正，則，以當前元素結尾的連續子數組和的最大值 = 當前元素 + 以前一個元素結尾的連續子數組和的最大值

否則，以當前元素結尾的連續子數組和的最大值 = 當前元素

比較以當前元素結尾的連續子數組和的最大值與當前全局最大值

Python

class Solution:def FindGreatestSumOfSubArray(self, array):if not array:return 0max_sum, cur_sum = array[0], 0for item in array:if cur_sum <= 0:cur_sum = itemelse:cur_sum += itemmax_sum = max(max_sum, cur_sum)return max_sum

Java

class Solution {public int maxSubArray(int[] nums) {if(nums.length <= 0) {return 0;}int maxSum = nums[0], curSum = nums[0];for(int i=1; i<nums.length; i++) {if(curSum < 0) {curSum = nums[i];} else {curSum += nums[i];}maxSum = curSum > maxSum ? curSum : maxSum;}return maxSum;} }

轉載于:https://www.cnblogs.com/renzongxian/p/7472124.html

總結

以上是生活随笔為你收集整理的连续子数组最大和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。