首页 > 代码库 > 每天进步一点点——求最大子序列和问题

每天进步一点点——求最大子序列和问题

2024-07-16 23:37:58   220人阅读

转载请说明出处：http://blog.csdn.net/cywosp/article/details/38493351


假设有如下整数数组 -10 5 0 8 -1 10 -10 100 -1 求其最大的子序列和。从该数组我们可以知道其子序列和最大的序列为5 0 8 -1 10 -10 100且等于112。（为方便起见，如果数组全是负数则最大和为0）


处理这个问题，我们可以有如下四种方法：
方法一：时间复杂度为O(N^3)
int MaxSubSum1(const std::vector<int>& vec)
{
    int max = 0;
    for (int i = 0; i < vec.size(); ++i) {
        for (int j = 0; j < vec.size(); ++j) {
            int sum = 0;
            for (int x = i; x <= j; ++x) {
                sum += vec[x];
            }
            if (sum > max) {
                max = sum;
            }
        }
    }
    return max;
}
该方法是求出所有子序列的和，然后在得出最大的和。

方法二：时间复杂度为O(N^2)
int MaxSubSum2(const std::vector<int>& vec)
{
    int max = 0;
    for (int i = 0; i < vec.size(); ++i) {
        int sum = 0;
        for (int j = i; j < vec.size(); ++j) {
            sum += vec[j];
            if (sum > max) {
                max = sum;
            }
        }
    }
    return max;
}
因为后一子序列的和为前面序列和加上后面一元素，所以在前面子序列和已被求出的情况下可以少一次循环

方法三：时间复杂度为O(N log(N))
int MaxSubSum3(const std::vector<int>& vec, int left, int right)
{
    if (right == left) {
        if (vec[left] > 0) {
            return vec[left];
        } else {
            return 0;
        }
    }
    int center = (right + left) / 2;
    int left_max_sum = MaxSubSum3(vec, left, center);
    int right_max_sum = MaxSubSum3(vec, center + 1, right);

    int left_sum = 0;
    int left_max = 0;
    for (int i = center; i >= left; --i) {
        left_sum += vec[i];
        if (left_sum > left_max) {
            left_max = left_sum;
        }
    }

    int right_sum = 0;
    int right_max = 0;
    for (int i = center + 1; i <= right; ++i) {
        right_sum += vec[i];
        if (right_sum > right_max) {
            right_max = right_sum;
        }
    }

    return std::max(std::max(left_max_sum, right_max_sum), (right_max + left_max));
}
该方法是左右划分数组，然后递归分别求出每个被划分数组的最大和

方法四：时间复杂度为O(N)
int MaxSubSum4(const std::vector<int>& vec)
{
    int sum = 0;
    int max = 0;
    for (int i = 0; i < vec.size(); ++i) {
        sum += vec[i];
        if (sum > max) {
            max = sum;
        } else if (sum < 0) {
            sum = 0;
        }
    }

    return max;
}
这种方法是最为高效的，一次扫描素组就能求出，具有这种特性的算法叫作联机算法（on-line algorithm）

#include <iostream>
#include <vector>
#include <stdlib.h>

int main(int argc, char const *argv[])
{
    if (argc < 2) {
        std::cout << "./program int ... int" << std::endl;
        return -1;
    }
    std::vector<int> vec;
    vec.reserve(argc - 1);
    for (int i = 0; i < argc - 1; ++i) {
        vec.push_back(strtol(argv[i + 1], nullptr, 10));
    }
    std::cout << MaxSubSum1(vec) << std::endl;
    std::cout << MaxSubSum2(vec) << std::endl;
    std::cout << MaxSubSum3(vec, 0, vec.size() - 1) << std::endl;
    std::cout << MaxSubSum4(vec) << std::endl;

    return 0;
}
编译g++ -std=c++11 main.cc -o sum
运行./sum -10 5 0 8 -1 10 -10 100 -1
输出如下：
112
112
112
112 


联系
我们