最大连续子数组和

xiaoxiao2021-02-28  10

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.

问题描述:输入一个整数数组,数组中有正数也有负数,一个或连续的多个整数组成一个子数组,求所有子数组的和的最大值。 求子数组的和的最大值,首先可以求出数组所有子数组的和,再逐一比较可以得到和的最大值。这是最直观易懂的一种解法。但是对一个长度为n的数组,总共有n(n+1)/2个子数组,计算所有子数组的和时间复杂度为O(n^2)。而当n较大时,这种算法是很难被用户接受的。 对于数组(a1, a2, a3, ……, an),设curSum为当前子数组(ai, ai+1, ……, aj)的和,令k = j + 1且k ≤ n, sum = 0表示初始时子数组和的最大值。

1、如果curSum + ak > sum,那么sum = curSum + ak

2、如果curSum + ak ≤ 0,说明curSum已经是子数组(ai, ai+1, ……, aj, ak) 的和的最大值,那么curSum = ak,sum保持不变,对应的子数组为(ai, ai+1, ……, aj)

以数组{-1, -2, 3, 10, -4, 7, -2, -5}为例,初始时sum =0, i = 0, curSum = 0

1)i = 0 curSum = -1 sum = -1 2)i = 1 curSum = -2 sum = -1 3)i = 3 curSum = 3 sum = 3 4)i = 4 curSum = 13 sum = 13 5)i = 5 curSum = 9 sum = 13 6)i = 6 curSum= 16 sum = 16 7)i = 7 curSum = 11 sum = 16 有了上述思路,不难写出时间复杂度为O(n)的算法。

PHP实现代码如下:

function maxSubArray($arr) { if (count($arr) < 1) return false; $dp = []; $sum = 0; $start = $end = 0; $curSum = $arr[0]; for ($i = 1; $i < count($arr); $i++) { if ($curSum <= 0) { $start = $i; // 记录更新子数组开始位置 $curSum = $arr[$i]; } else { $curSum += $arr[$i]; } if ($curSum > $sum) { $sum = $curSum; $end = $i; // 记录并更新子数组结束位置 } } echo $start.'--'.$end; var_dump(array_slice($arr, $start, $end - $start + 1)); return $sum; } echo maxSubArray([-2,1,-3,4,-1,2,1,-5,4]);
转载请注明原文地址: https://www.6miu.com/read-1100182.html

最新回复(0)