最大子序列算法[整理].pdf

最大子序列问题是一种经典的算法问题，它涉及到对一维数组中的连续子序列进行求和，目标是找到和最大的那个子序列。在这个问题中，我们通常使用动态规划的思想来解决。以下是对最大子序列求和算法的详细解释： 1. **算法描述**： - 初始化变量`max`为0，用于存储当前找到的最大子序列和；`sum`初始化为0，表示当前子序列的和；`begin`和`finish`分别记录当前子序列的起始和结束位置。 - 遍历数组，每次迭代将当前元素`arr[i]`加到`sum`中，并更新`finish`。 - 如果`sum`大于`max`，则更新`max`为`sum`，同时更新`start`和`end`为当前子序列的起始和结束位置。 - 如果`sum`小于等于0，说明当前子序列不再具有增加和的可能性，需要丢弃前面的子序列，重新开始一个新的子序列，因此将`sum`置0，并将`begin`设置为`i+1`。 - 遍历结束后，返回`max`作为最大子序列的和。 2. **代码实现**： - 提供的代码使用了C++实现，通过`MaxSubSeq`函数找到最大子序列和以及起始和结束位置。在`main`函数中，给出了一个示例数组，并调用`MaxSubSeq`函数打印出最大子序列的位置和和。 3. **最长公共子串（LCS）**： - LCS问题要求找出两个字符串之间的最长连续子串，这个子串同时存在于两个原始字符串中。 - 采用动态规划的方法，创建一个二维矩阵，矩阵的大小与两个字符串的长度相关。矩阵中的每个元素表示对应位置的两个字符是否相同，如果相同则该位置的值为前一个元素加1，否则为0。 - 找到矩阵中斜对角线上的最大值，对应的子串长度即为LCS的长度。为了节省空间，可以只保留上一行的数据，因为当前行的数据依赖于上一行，但上一行数据不会再次被引用。 4. **代码实现**： - 提供的LCS代码同样使用C++实现，定义了一个名为`LCS`的函数，接收两个字符串作为参数，返回它们的最长公共子串。 - 使用`vector<int>`动态构建矩阵的当前行，初始化为0，然后遍历第二个字符串，比较每个字符与第一个字符串中相应位置的字符，如果相同则更新矩阵元素并检查当前元素是否大于最大值。 - 在循环结束后，根据最大值和当前位置，从第一个字符串中提取最长公共子串。 这两个算法都体现了动态规划的核心思想，通过构建中间状态并利用前一状态的信息，逐步解决问题。在实际编程中，动态规划经常被用来解决最优化问题，如寻找最优路径、计算组合计数等。掌握这类问题的解决方法对于提升编程能力及解决复杂问题有着重要的作用。