weixin_42042460
2018-04-24 13:41
采纳率: 63.6%
浏览 1.2k
已采纳

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

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

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • devmiao 2018-04-24 14:38
    已采纳
     #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;
    }
    
    点赞 打赏 评论

相关推荐 更多相似问题