在计算机科学中，最大子串问题是求一个给定数组的连续子数组，该子数组的元素之和最大。这是一个经典的问题，在算法中有许多解题方法。例如，使用分治法递归完整数组或将问题简化为它的子问题，或者动态规划解法在O（n）时间中解决问题。另外一些算法为暴力搜索，最坏时间复杂度为O(n^2)，但以O(n)的平均时间进行。
举例来说，对于数组{−2, 1, −3, 4, −1, 2, 1, −5, 4}，最大子串应该是{4, −1, 2, 1}，其元素和为6。
最大子串问题是许多其他问题的基础，例如最长公共子序列问题，最大子矩阵问题和启发式搜索等。它还在数学分析和计算机算法设计方面具有广泛应用。
该问题由Ulf Grenander于1977年提出，并被证明在时空复杂性理论上有趣。
了解更多有趣的事情：https://blog.ds3783.com/