寻找数组最大子序和是一道非常经典的算法题目,其中经典的做法是通过动态规划求解,今天我将分享在做这道题的时候的一些思路。这道题的题干也是相当简单,就是给出一个数组,然后让你给出这个数组中最大的连续子数组的和。以[-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!
评论(0)
您还未登录,请登录后发表或查看评论