算法第三章上机实践报告

本文主要是介绍算法第三章上机实践报告，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时，定义子段和为0。

要求算法的时间复杂度为O(n)。

创建一个新数组，其每一项的值都是以数组a中对应元素结尾的序列的最大字段和。最后返回新数组中的最大值，即问题的解。

\[max(1 \leq i \leq j )\sum_{k=i}^{j}{a[k]} = max(1\leq j\leq n ) b[j] \]

\[b[j] = max(b[j-1]+a[j],a[j]) \]

一维表，0 - n，从左至右。

时间复杂度：O(n)

空间复杂度：O(n)

解决动态规划问题时要找准递归方程，dp数组的范围和初始化方式也很关键。

类似用空间换取时间，有分治法的影子，但避免了大量的重复运算，大大提高了运算效率。

这篇关于算法第三章上机实践报告的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程