東十八北面的天空.jpg

原題：使用如下思想為最大子數(shù)組問題設(shè)計(jì)一個(gè)非遞歸的、線性時(shí)間的算法邢疙。從數(shù)組的左邊界開始肮柜，由左至右處理陷舅，記錄到目前為止已經(jīng)處理過得最大子數(shù)組。若已知A[1…j]的最大子數(shù)組审洞，基于如下性質(zhì)將解擴(kuò)展為A[1…j+1]的最大子數(shù)組：A[1…j+1]的最大子數(shù)組要么是A[1…j]的最大子數(shù)組莱睁，要么是某個(gè)子數(shù)組A[i…j+1] (1≤i≤j+1)。在已知A[1…j]的最大子數(shù)組的情況下芒澜，可以在線性時(shí)間內(nèi)找到形如A[i…j+1]的最大子數(shù)組仰剿。

思路：題目點(diǎn)出一個(gè)很重要的思路就是新數(shù)組的最大子數(shù)組，必然是2種情況之一：
1.依然是[1,j]數(shù)組的最大子數(shù)組;
2.[i,j+1]這樣一個(gè)最大子數(shù)組(0<=i<=j+1);
所以關(guān)鍵點(diǎn)就成了痴晦，如何去尋找第二種情況：
在解第二種情況的時(shí)候南吮，有一點(diǎn)要考慮到，就是如果一段子數(shù)組[i,j]的和<0誊酌，則最大子數(shù)組不可能為[i,j+1]部凑，因?yàn)閟um[i,j+1]<[j+1];
利用這個(gè)結(jié)論，我們可以對(duì)數(shù)組進(jìn)行線性求和碧浊，若和<0則拋棄目前計(jì)算的子數(shù)組涂邀，將子數(shù)組的和重置為0，順下去去找新的子數(shù)組箱锐，左邊界的leftIndex也重置為當(dāng)前index比勉。
若計(jì)算中的子數(shù)組的和大于目前最大子數(shù)組，則更新最大子數(shù)字的sum,并更新右邊界驹止。
以下是c語言實(shí)現(xiàn)代碼浩聋，復(fù)雜度為O(n):

//線性求解最大自數(shù)組的問題
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int *linearMaximumSubarray(int arr[], int low, int high); //線性尋找最大子數(shù)組

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("最大跨界子數(shù)組的和為%d", result[2]);
    free(result);
    return 0;
}
//返回最大自數(shù)組的左右邊界和最大子數(shù)組的和
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;
}