简述求子数组的最大和 ？

求子数组的最大和问题通常可以使用动态规划或分治法来解决。这里，我将简要介绍这两种方法：

1. 动态规划法：

   • 初始化一个变量 max_sum 为数组的第一个元素，另一个变量 current_sum 也为数组的第一个元素。
   • 从数组的第二个元素开始遍历。
   • 对于每个元素，比较 current_sum + 当前元素 和 当前元素 的大小，将较大的值赋给 current_sum。
   • 然后比较 current_sum 和 max_sum 的大小，将较大的值赋给 max_sum。
   • 遍历结束后，max_sum 就是子数组的最大和。
   • 时间复杂度为 O(n)，其中 n 是数组的长度。

2. 分治法：

   • 将数组分为两个子数组，递归地求两个子数组的最大和。
   • 同时，考虑跨越两个子数组的子数组，即包含两个子数组第一个和最后一个元素的子数组。
   • 最后，比较这三个和的大小，取最大值作为整个数组的最大和。
   • 时间复杂度为 O(log n)，其中 n 是数组的长度，但由于需要计算跨越两个子数组的和，实际的时间复杂度可能会更高。

这两种方法都可以用来求子数组的最大和，但动态规划法更简单且在实际应用中更为常用。