最大连续子数组和

    例如输入的数组为，和最大的子数组为，
    因此输出为该子数组的和18。

    求一个数组的最大子数组和，我想最直观最野蛮的办法便是，三个for循环三层遍历，求出数组中每一个子数组的和，最终求出这些子数组的最大的一个值。
    令currSum[i, …, j]为数组A中第i个元素到第j个元素的和（其中0 <= i <= j < n），maxSum为最终求到的最大连续子数组的和。

    且当全是负数的情况时，我们可以让程序返回0，也可以让程序返回最大的那个负数，这里，我们让程序返回最大的那个负数。

    参考代码如下：

    此方法的时间复杂度为O(n^3)。

    解法二

    事实上，当我们令currSum为当前最大子数组的和，maxSum为最后要返回的最大子数组的和，当我们往后扫描时，

    • 对第j+1个元素有两种选择：要么放入前面找到的子数组，要么做为新子数组的第一个元素；
      • 如果currSum加上当前元素a[j]后不小于a[j]，则令currSum加上a[j]，否则currSum重新赋值，置为下一个元素，即currSum = a[j]。
    • 同时，当currSum > maxSum，则更新maxSum = currSum，否则保持原值，不更新。

    即

    • maxSum ： 0 1 1 3 13 13 16 18 18

    参考代码如下：

    1. 如果数组是二维数组，同样要你求最大子数组的和列?
    2. 如果是要你求子数组的最大乘积列?
    3. 如果同时要求输出子段的开始和结束列?

    1 给定整型数组，其中每个元素表示木板的高度，木板的宽度都相同，求这些木板拼出的最大矩形的面积。并分析时间复杂度。

    此题类似leetcode里面关于连通器的题，需要明确的是高度可能为0，长度最长的矩形并不一定是最大矩形，还需要考虑高度很高，但长度较短的矩形。如[5,4,3,2,4,5,0,7,8,4,6]中最大矩形的高度是[7,8,4,6]组成的矩形，面积为16。

    2、环面上的最大子矩形

    《算法竞赛入门经典》 P89 页。

    3、最大子矩阵和

    一个MN的矩阵，找到此矩阵的一个子矩阵，并且这个子矩阵的元素的和是最大的，输出这个最大的值。如果所有数都是负数，就输出0。
    例如：3    5的矩阵：

    2 3 4 5 1

    1 1 5 3 0

    和最大的子矩阵是：

    4 5

    5 3

    最后输出和的最大值17。

    4、允许交换两个数的位置 求最大子数组和。