最大子数和

A. 暴力求解法——$O(N^2)$

1. 题目信息

  • 输入是一个整数数组，返回是一个整数；
  • 返回的整数：一个连续子数组的和（一个连续子数组 = 一组连续的下标）；
  • 如果输入的数组不为空，则返回的整数不为空；

2. 算法思路

  • 使用暴力枚举对所有可能的头部指针i 和尾部指针j，求$sum(nums[i,j])$，记录其中最大的值放入maxSum变量中（i <= j）。

3. 超时优化思路：

  • nums中每个“极大的”连续的“正负性”相同的连续子数组，要么都在解中，要么都不在解中。

    -1,-2,3,4,5,6,-7 【3,4,5,6为局部极大】

    假设如果[x, x+1]为正负性相同的两个下标，并且x+1在解中，x不在。

    1）nums[x] > 0。如果将x放入解中，解的大小会变大，与解是最大值违背。

    2）nums[x]< 0。nums[x+1]< 0, 解中剔除nums[x+1]，解会变大。

4. 小结

  • 数组压缩的思想

B 贪心法

1. 算法思想

对解的区间$[i,j]$的讨论

1）$nums[i]>0$ 并且$nums[i-1]<0$;

2）不存在$k\in[i,j]$，使得$sum(nums[i, k])<0$；

3）不存在$k\in[0,i-1]$，使得$sum(nums[k,i-1])>0$;

“贪心算法”能够帮助我们找到解的起始下标i：当扫描指针来到解的起始下标时，当前和一定是等于0.

C 动态规划

1. 算法思想

贪心和动态规划

  • 共同点：

1）基于子问题求解（无后效性）；

2）策略驱动。

  • 不同点：

1）贪心：局部最优可以得到全局最优；解具备一定的单调性

2）动态规划：每个子问题可能会记录多种状态不一定只存储最优；对解的单调性要求不高。

子问题的切割：大部分情况下都是比较自然。

D 分治法

1 分治法讲解

  • 问题递归分割：分治法会将原问题分成N个子问题分别进行求解。如果子问题的规模依旧非常大（不能直观的得到答案的规模），那么需要对子问题递归地进行分割。

    +++ 问题的规模/大小实际是指输入的实例（输入到算法中具体的例子）；

  • 临界问题求解：可以“简单”求解的问题。一般对临界问题的求解消耗的时间都是$O(1)$。

  • 子问题解的合并：当已知子问题的解时，如果通过这些解得到父问题的答案。

算法核心：将大化小，对小问题进行求解，从而求解出原问题。

算法的难点：如何切割，以及如何将解合并。

分治法的重要思想：假设当前已经拥有子问题的解。

2 算法思路

  • 子问题的解与父问题的解

    （1）父问题S的解在左实例S1中：递归地求解S1

    （2）父问题S的解在右实例S2中：递归地求解S2

    （3）父问题S的解被分在左右两个实例中：

    ​ 3.1 在S1中，求解是以i作为解的右下标的解区间；

    ​ 3.2 在S2中，求解是以i+1作为解的坐下标的解区间；

  • 如果问题的规模为1，就意味着输入的数组只含有一个整数；

3 总结

  1. 暴力求解->压缩数组->极大连续同正负性数可以合并（非全负case）->当序列的第一位是负数的时候，可以抛弃；
  2. 贪心方案->是要当前和是正数，那么就可以考虑加和下一位，当前的加和序列依旧有潜力成为最大和。
  3. 动态规划：对变种的最大子数和问题的一个思考；