寻找数组最大子序和是一道非常经典的算法题目,其中经典的做法是通过动态规划求解,今天我将分享在做这道题的时候的一些思路。这道题的题干也是相当简单,就是给出一个数组,然后让你给出这个数组中最大的连续子数组的和。以[-2,1,-3,4,-1,2,1,-5,4]为例。

1、暴力解法

暴力解法之所以能够称之为暴力解法,就是因为并不需要任何技巧,就是从头遍历每个元素,得到从这个元素开始到最后一个元素之间的总和。选择最大的那个和就是可以。代码如下所示:

#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int> data = {-2,1,-3,4,-1,2,1,-5,4};
    int tmp = 0;
    int max_tmp = 0;
    for(int i = 0;i<data.size();i++){
        for(int j = i;j<data.size();j++){
            tmp = tmp+data[j];  
            if(tmp>max_tmp){
                max_tmp = tmp;
            }
        }
        tmp = 0;
    }
    cout<<max_tmp<<endl;
    return 0;
}

每次i都会依次增加,而j则从i处开始。累加data[j]的值,只要在累加过程中出现和大于当前最大值的情况就需要将其记录。接触输出为6。

2、提前终止的暴力解法

在上面的暴力解法中,每一步都会从i坐标处开始,一直累加到数组最后。但是其实如果i坐标处的值小于0,那么我们就可以直接从i+1处开始,因为如果i+i处的坐标大于零,那么从i+i开始的值一定会大于从i开始累加的值。

#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int> data = {-3,-3,-7,-1,-8};
    int tmp = data[0];
    int max_tmp = data[0];
    for(int i = 0;i<data.size();i++){
        if(data[i]<0){
            if(data[i]>max_tmp)
                max_tmp = data[i];
            continue;
        }
        for(int j = i;j<data.size();j++){
            tmp = tmp+data[j];  
            if(tmp>max_tmp)
                max_tmp = tmp;
        }
        tmp = 0;
    }
    cout<<max_tmp<<endl;
    

在这里我们只需要在每次遍历i的时候判断一下data[i]是否小于0即可,若小于零,则使用continue,跳过后面的for循环,重新从i+1处开始。但是这里需要注意,为了防止原数组的值都小于0的情况,需要在判断出data[i]小于零的同时,判断data[i]与当前最大值的大小。结果输出为-1.

3、动态规划

动态规划算法是解此类问题的经典做法,通过维护一个动态规划数组dp,来得到之前子序和的最大值。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    vector<int> data = {-2,1,-3,4,-1,2,1,-5,4};
    vector<int> dp;
    dp.push_back(data[0]);
    for(int i = 1;i<data.size();i++)
    {
        dp.push_back(dp[i-1]<=0?data[i]:dp[i-1]+data[i]);
    }
    cout<<*max_element(dp.begin(),dp.end())<<endl;
    return 0;
}

这里用到了algorithm库中的迭代器,当前其实不用也可以,只要每一步都判断一下。这里的实现思路就是判断之前最大值是否小于零,如果小于零的话,那前面的这一步之前的最大值就是当前值。即使是全小于零的值,也可以在后面的选最大值的过程中得到最大的那个负数。

4、改变原数组

这种解法

#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int> data = {-2,1,-3,4,-1,2,1,-5,4};
    int tmp = 0;
    for(int i = 1;i<data.size();i++)
    {
        if(data[i-1]<0)
            data[i] = data[i];
        else
            data[i] = data[i]+data[i-1];
        if(data[i]>tmp)
            tmp = data[i];     
    }
    cout<<tmp<<endl;
    return 0;
}

这种解法同时结合了动态规划算法高效以及暴力解法小内存的优点,摒弃了动态规划算法需要额外定义数组以及暴力解法耗时长的缺点。其本质就是简化版的动态规划。

May the force be with you!