如何求数组连续最大和？

轩辕小不懂发布于 2022-03-28 11:41

阅读 556

答案 1

分类：人工智能

人工智能

python

编程论坛

一个有n个元素的数组，这n个元素既可以是正数也可以是负数，数组中连续的一个或多个元素可以组成一个连续的子数组，一个数组可能有多个这种连续的子数组，求子数组和的最大值。例如：对于数组[1,-2, 4, 8,-4, 7,-1,-5]而言，其最大和的子数组为[4, 8,-4, 7]，最大值为15。

3385

Nen 2022-03-28 14:06

- 程序员

动态规划方法可以采用动态规划的方法来降低算法的时间复杂度。实现思路如下。首先可以根据数组的最后一个元素arr[n-1]与最大子数组的关系分为以下三种情况讨论：

1）最大子数组包含arr[n-1]，即最大子数组以arr[n-1]结尾。

2）arr[n-1]单独构成最大子数组。

3）最大子数组不包含arr[n-1]，那么求arr[1…n-1]的最大子数组可以转换为求arr[1…n-2]的最大子数组。

通过上述分析可以得出如下结论：假设已经计算出子数组arr[1…i-2]的最大的子数组和All[i-2]，同时也计算出arr[0…i-1]中包含arr[i-1]的最大的子数组和为End[i-1]。则可以得出如下关系：All[i-1]=max(End[i-1],arr[i-1],All[i-2])。利用这个公式和动态规划的思想可以得到如下代码：