分治法求最大非连续子序列

Question

求非连续子序列的问题用DP很好解决，但是**分治法**就比较难了
假设有一个序列是L = [1, 0, 5, 3, 2, 7, 9, 15, 6, 4, 13]
他的最大非连续子序列就是 S = [1, 5, 7, 15, 13] 俩俩数字任意不相邻
现在要求给L求S

Answer 1

 #include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_N 20

int max3(int, int, int);
int maxSubArrayAns(int []);
int maxSubArray(int [], int, int);

int main(){
    int nums[MAX_N];
    int i;
    srand(time(0));
    printf("array: \n");
    for(int i = 0; i < MAX_N; i++){
        nums[i] = (int)(rand() % (MAX_N * 2) - MAX_N);
        printf("%d\t", nums[i]);
    }
    printf("\n");
    printf("The max subsequen sum is %d.\n", maxSubArrayAns(nums));


    return 0;
}

int max3(int a, int b, int c){
    if(a > b)
        return a > c ? a : c;
    else
        return b > c ? b : c;
}

int maxSubArray(int nums[], int left, int right){
    int maxLeftSum, maxRightSum;
    int maxLeftBorderSum, maxRightBorderSum;
    int leftBorderSum, rightBorderSum;

    if(left == right)
        if(nums[left] > 0)
            return nums[left];
        else
            return 0;

    int mid = (left + right) / 2, i;
    maxLeftSum = maxSubArray(nums, left, mid);
    maxRightSum = maxSubArray(nums, mid + 1, right);

    maxLeftBorderSum = 0, leftBorderSum = 0;
    for(i = mid; i >= left; i--){
        leftBorderSum += nums[i];
        if(leftBorderSum > maxLeftBorderSum)
            maxLeftBorderSum = leftBorderSum;
    }

    maxRightBorderSum = 0, rightBorderSum = 0;
    for(i = mid + 1; i <= right; i++){
        rightBorderSum += nums[i];
        if(rightBorderSum > maxRightBorderSum)
            maxRightBorderSum = rightBorderSum;
    }

    return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
}

int maxSubArrayAns(int nums[]){
    return maxSubArray(nums, 0, MAX_N - 1);
}

使用分治法的话，平均时间复杂度为Θ(n lg n)。实际上解决最大子序列问题还有一种更加快速的方法，这种方法的时间复杂度是Θ(n)，是一种线性的算法

 int maxSubArrayAns(int nums[]){
    int i, thisSum = 0, maxSum = 0;
    for(i = 0; i < MAX_N - 1; i++){
        thisSum += nums[i];
        if(thisSum > maxSum)
            maxSum = thisSum;
        else if(thisSum < 0)
            thisSum = 0;
    }

    return maxSum;
}