算法导论4.1.5:线性查找最大子数组问题

东十八北面的天空.jpg

原题：使用如下思想为最大子数组问题设计一个非递归的、线性时间的算法。从数组的左边界开始，由左至右处理，记录到目前为止已经处理过得最大子数组。若已知A[1…j]的最大子数组，基于如下性质将解扩展为A[1…j+1]的最大子数组：A[1…j+1]的最大子数组要么是A[1…j]的最大子数组，要么是某个子数组A[i…j+1] (1≤i≤j+1)。在已知A[1…j]的最大子数组的情况下，可以在线性时间内找到形如A[i…j+1]的最大子数组。

思路：题目点出一个很重要的思路就是新数组的最大子数组，必然是2种情况之一：
1.依然是[1,j]数组的最大子数组;
2.[i,j+1]这样一个最大子数组(0<=i<=j+1);
所以关键点就成了，如何去寻找第二种情况：
在解第二种情况的时候，有一点要考虑到，就是如果一段子数组[i,j]的和<0，则最大子数组不可能为[i,j+1]，因为sum[i,j+1]<[j+1];
利用这个结论，我们可以对数组进行线性求和，若和<0则抛弃目前计算的子数组，将子数组的和重置为0，顺下去去找新的子数组，左边界的leftIndex也重置为当前index。
若计算中的子数组的和大于目前最大子数组，则更新最大子数字的sum,并更新右边界。
以下是c语言实现代码，复杂度为O(n):

//线性求解最大自数组的问题
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int *linearMaximumSubarray(int arr[], int low, int high); //线性寻找最大子数组

int main()
{
    int arr[16] = {13, -3, -25, 1, -3, 16, 23, 18, -20, -7, -12, -50, -22, 15, -4, 7};
    int *result = linearMaximumSubarray(arr, 0, 15);
    printf("左边界为%d", result[0]);
    printf("右边界为%d", result[1]);
    printf("最大跨界子数组的和为%d", result[2]);
    free(result);
    return 0;
}
//返回最大自数组的左右边界和最大子数组的和
int *linearMaximumSubarray(int arr[], int low, int high)
{
    int *a = calloc(3, sizeof(int));
    int sum = INT_MIN;
    int leftIndex = low;
    int rightIndex = low;
    int subArraySum = 0;
    int subLeftIndex = low;
    for (int i = low; i <= high; i++)
    {
        subArraySum += arr[i];
        if (subArraySum > sum)
        {
            sum = subArraySum;
            leftIndex = subLeftIndex;
            rightIndex = i;
        }
        if (subArraySum < 0)
        {
            subArraySum = 0;
            subLeftIndex = i + 1;
        }
    }

    a[0] = leftIndex;
    a[1] = rightIndex;
    a[2] = sum;
    return a;
}