最大子列和 —— 时间 O(n^3) -> O(n^2) ->

• 写的超棒的reference
• 浙大数据结构
  ⚠️ 若某段序列中都是负数，最大子列和是0，该子列长度为0，因此max_sum初始是0

• 分治的时空复杂度分析

• 分治(算法3)，时间O(nlgn)
  空间复杂度：递归栈深度O(lgn),存储原始数组O(n),整体为O(n+lgn) = O(n)

下面四种实现依次为 时间O(n^3) -> O(n^2) -> O(nlgn) -> O(n)

O(n)一定是最快的一级了，怎么着也要扫描一遍的。。。

#include <cstdio>
#include <ctime>
#include <algorithm>

using namespace std;
const int M = 10;
const int SIZE = 1000;
int data[SIZE] = {717};
clock_t start, stop;
double duration;

int max_subseq_sum_1(const int seq[], int size) {
    int max_sum = 0;
    for (int i = 0; i < size; ++i) {
        for (int j = i; j < size; ++j) {
            int sum = 0;
            for (int k = i; k <= j; ++k) {
                sum += seq[k];
            }
            max_sum = max(max_sum, sum);
        }
    }
    return max_sum;
}

int max_subseq_sum_2(const int seq[], int size) {
    int max_sum = 0;
    for (int i = 0; i < size; ++i) {
        int sum = 0;
        for (int j = i; j < size; ++j) {
            sum += seq[j];
            max_sum = max(max_sum, sum);
        }
    }
    return max_sum;
}

// divide and conquer
int conquer(const int seq[], int st, int ed) {
    if (st < ed) {
        /*
         * 最大子列和可能出现在
         * 1. st - mid
         * 2. mid+1 - ed
         * 3. 跨越分界 （含mid 和 mid+1的一段序列）
         *      求出含mid的左部最大子序列和 含mid+1的右部最大子序列和 相加即可
         * 取三者中最大的
         */
        int mid = (st + ed) / 2;
        int res1 = conquer(seq, st, mid);
        int res2 = conquer(seq, mid + 1, ed);
        int lsum_with_last = seq[mid], rsum_with_first = seq[mid + 1];
        int lsum = lsum_with_last, rsum = rsum_with_first;
        for (int i = mid - 1; i >= st; --i) {
            lsum += seq[i];
            lsum_with_last = max(lsum, lsum_with_last);
        }
        for (int i = mid + 2; i <= ed; ++i) {
            rsum += seq[i];
            rsum_with_first = max(rsum, rsum_with_first);
        }
        int res3 = lsum_with_last + rsum_with_first;
        return max(max(res1, res2), res3);
    } else {
        return seq[st];
    }
}

int max_subseq_sum_3(const int seq[], int size) {
    return conquer(seq, 0, size - 1);
}

//在线处理
int max_subseq_sum_4(const int seq[], int size) {
    int max_sum = 0, sum = 0;
    for (int i = 0; i < size; ++i) {
        sum += seq[i];
        sum > 0 ? max_sum = max(sum, max_sum) : sum = 0;
    }
    return max_sum;
}

int main() {
//    printf("%d", CLOCKS_PER_SEC);
    int res1, res2, res3, res4;
    for (int i = 1; i < SIZE; ++i) {
        data[i] = data[i - 1] / 2 - 1000 + i * i;
    }
    start = clock();
    for (int i = 0; i < M; ++i) {
        res1 = max_subseq_sum_1(data, SIZE);
    }
    stop = clock();
    duration = (double) (stop - start) / CLOCKS_PER_SEC;
    printf("res1 %d  duration 1 : %lf sec\n", res1, duration);

    start = clock();
    for (int i = 0; i < M; ++i) {
        res2 = max_subseq_sum_2(data, SIZE);
    }
    stop = clock();
    duration = (double) (stop - start) / CLOCKS_PER_SEC;
    printf("res2 %d  duration 2 : %lf sec\n", res2, duration);

    start = clock();
    for (int i = 0; i < M; ++i) {
        res3 = max_subseq_sum_3(data, SIZE);
    }
    stop = clock();
    duration = (double) (stop - start) / CLOCKS_PER_SEC;
    printf("res3 %d  duration 3 : %lf sec\n", res3, duration);

    start = clock();
    for (int i = 0; i < M; ++i) {
        res4 = max_subseq_sum_4(data, SIZE);
    }
    stop = clock();
    duration = (double) (stop - start) / CLOCKS_PER_SEC;
    printf("res4 %d  duration 4 : %lf sec\n", res4, duration);
    return 0;
}
/*
 * 10 * 1000
 * res1 661720035  duration 1 : 3.117018 sec
 * res2 661720035  duration 2 : 0.019138 sec
 * res3 661720035  duration 3 : 0.000488 sec
 * res4 661720035  duration 4 : 0.000038 sec
 */

作业题

时O(n) 空O(1)，网页上直接写ac了😄

另一题，二分

喜欢这种没编译就交上去a了的感觉🐶