最大子数组

源自《算法导论》中的题目，利用分治和动态规划可以解决此问题

1. 题目描述

假定你获得了投资挥发性化学公司的机会。与其生产的化学制品一样，这家公司的股票价格也是不稳定的。你被准许可以在某个时刻买进一股该公司的股票，并在之后某个日期将其卖出，买进卖出都是在当天交易结束后进行。为了补偿这一限制，你可以了解股票将来的价格。你的目标是最大化收益。

现在给出了17天内，每天交易结束后，挥发性化学公司的股票价格信息。横轴表示日期，纵轴表示股票价格。表格的最后一行给出了股票价格相对于前一天的变化

第0天的股票价格是每股100美元，可以在此之后任何时间买进股票。我们当然希望“低价买进，高价卖出”——在最低价格时买进股票，之后在最高价格时卖出，这样可以最大化收益。但遗憾的是，在一段给定时期内，可能无法做到在最低价格时买进股票，然后在最高价格时卖出。例如，在上图中，最低价格发生在第7天，而最高价格发生在第1天——最高价在前，最低价在后。

你可能认为可以在最低价格时买进，或在最高价格时卖出，即可最大化收益。例如，在上图中，我们可以在第7天股票价格最低时买入，即可最大化收益。如果这种策略总是有效的，则确定最大化收益是非常简单的：寻找最高和最低价格，然后从最高价格开始向左寻找之前的最低价格，从最低价格开始向右寻找之后的最高价格，取两对价格中差值最大者。但在下图中我们将给出了一个简单的反例，显示有时最大收益既不是在最低价格时买进，也不是在最高价格时卖出。

通过上图我们发现，真正的最大收益是在第2天买进，第三天卖出，而这两天的股票价格并非历史最高或者历史最低

暴力求解？

我们确实可以通过暴力穷举所有日期的买进和卖出情况，只要符合卖出在买进日期之后即可，n天的话共有$C_n^2$种情况，时间复杂度$O(n^2)$，不做考虑

换个脑子想问题

我们将从一个稍微不同的角度来看待输入数据。我们的目的是寻找一段日期，使得从第一天到最后一天的股票价格差值最大。因此，我们不再从每日价格的角度去看待输入数据，而是考察每日价格变化，第i天的价格变化定义为第i天和第i-1天的价格差。那么问题就转化为求最大的非空连续子数组的和。我们称这样的连续子数组为最大子数组(maximum subarray)。例如，如下图中的数组，A[1..16]的最大子数组为A[8..11]，其和为43。因此，你可以在第8天（7天之后）买入股票，并在第11天后卖出，获得每股收益43美元。

需要注意的时，只有当数组中包含负数时，最大子数组问题才有意义。如果所有数组元素都是非负的，最大子数组问题没有任何难度，因为整个数组的和肯定是最大的

分治法策略

假定我们要寻找子数组A[left...lefright]的最大子数组。使用分治技术意味着我们要将子数组划分为两个规模尽量相等的子数组。也就是说，找到子数组的中央位置，比如mid，然后考虑求解两个子数组A[low..high]和A[mid+1...right]。如图4-4(a)所示，A[low..high]的任何连续子数组A[i..j]所处的位置必然是以下三种情况之一：

• 完全位于子数组A[low..mid]中，因此low<=i<=j<=mid。
• 完全位于子数组A[mid+1..high]中，因此mid
• 跨越了中点，因此low<=i<=mid

可以肯定的是，A[low..high]的一个最大子数组必然是完全位于A[low..mid]中、完全位于A[mid+1..high]中活着跨越中点的所有子数组中和最大者。我们可以递归地求解A[low..mid]和A[mid+1..high]的最大子数组，因为这两个子问题仍是最大子数组问题，只是规模更小。因此，剩下的全部工作就是寻找跨越中点的最大子数组，然后在三种情况中选取和最大者。

我们可以从中间位置开始，分别向左和向右两个方向进行操作，通过累加找到两个方向的最大和，分别为l_max和r_max，因此存在于中间的最大和为（l_max+r_max）；

具体代码可以如下：

def get_max_cross_mid(arr, left, mid, right):
    l_max = 0
    r_max = 0
    sum = 0
    for i in range(mid, left - 1, -1):
        sum += arr[i]
        if l_max < sum:
            l_max = sum
    sum = 0
    for i in range(mid + 1, right + 1):
        sum += arr[i]
        if r_max < sum:
            r_max = sum
    return l_max + r_max

很明显，我们可以在线性时间内完成指定区间内跨越中点的最大子数组的和

接下来我们可以将问题分解为规模更小的子问题，如下代码即可：

def get_max(arr, left, right):
    if left == right:
        return arr[left]
    else:
        mid = (left + right) >> 1
        l_max = get_max(arr, left, mid)
        r_max = get_max(arr, mid + 1, right)
        c_max = get_max_cross_mid(arr, left, mid, right)
        return max([l_max, r_max, c_max])

时间复杂度

从上述的代码来看，我们完成了基本的最大子数组的和的问题求解，其符合的公式如下：

$$T(n)=2T(n/2)+\Theta(n)$$
利用主定理公式求解：
$$T(n)=\Theta(n\log_2 n)$$

如果要同时统计最大子数组的起始和终止位置，如下：

def get_max_cross_mid(arr, left, mid, right):
    l_max = 0
    r_max = 0
    sum = 0
    l_index = mid
    for i in range(mid, left - 1, -1):
        sum += arr[i]
        if l_max < sum:
            l_max = sum
            l_index = i
    sum = 0
    r_index = mid + 1
    for i in range(mid + 1, right + 1):
        sum += arr[i]
        if r_max < sum:
            r_max = sum
            r_index = i
    return l_index, r_index, l_max + r_max
def get_max(arr, left, right):
    if left == right:
        return left, right, arr[left]
    else:
        mid = (left + right) >> 1
        left_data = get_max(arr, left, mid)
        right_data = get_max(arr, mid + 1, right)
        cross_data = get_max_cross_mid(arr, left, mid, right)
        if left_data[2] >= right_data[2] and left_data[2] >= cross_data[2]:
            return left_data
        elif right_data[2] >= left_data[2] and right_data[2] >= cross_data[2]:
            return right_data
        else:
            return cross_data