问题描述:给一个数组,有正有负,求其连续子序列的最大值
解法1:穷举暴力法 枚举左端点跟右端点,然后遍历更新所有的子序列和,最终得到结果就是最大的
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],b[N];
int n ;
int ans ;
const int INF = 0x3f3f3f;
int main()
{
int n;
cout<<"please input size"<<endl;
cin>>n;
cout<<"please input data"<<endl;
for(int i =1;i<=n;++i)
{
cin>>a[i];
}
int ans = -INF;
for(int i =1;i<=n;++i)
{
for(int j =i;j<=n;++j)
{
int sum = 0;
for(int k=i;k<=j;++k)
{
sum+=a[k];
}
ans = max(ans,sum);
}
}
cout<<ans<<endl;
return 0;
}
解法2:单调队列求解
思路:维护一个单调递增的前缀和队列,队首元素是整个序列的最小值,维护队列的同时,用前缀和的元素减去这个最小值,得到值最大,为这数组的子序列的最大值
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],b[N];
int n ;
int ans ;
const int INF = 0x3f3f3f;
deque<int> q;
int main()
{
int n;
cout<<"please input size"<<endl;
cin>>n;
cout<<"please input data"<<endl;
for(int i =1;i<=n;++i)
{
cin>>a[i];
}
q.push_back(0),b[0] = 0;
for(int i =1;i<=n;++i)
{
b[i] = b[i-1]+a[i];
ans = max(ans,b[i]-b[q.front()]);
while(!q.empty()&&b[i]<=b[q.back()])
q.pop_back();
q.push_back(i);
}
cout<<ans<<endl;
return 0;
}
解法3:分治法 思路:分三种情况讨论 1.计算left到k的和的和,记作left_sum; 2.计算k+1到right的和,记作right_sum; 3.跨边界和,以k为中心向两边分别求和 1.从中心向左扩张一步,记录当前sum1,并于上一步对比, 若大于,则更新left 2.从中心向右扩张一步,记录当前sum2,并于上一步对比, 若大于,则更新right 3.计算连续字段和 sum = sum1+sum2; 计算完后,取三者最大值
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],b[N], dp[N];;
int n ;
int ans ;
const int INF = 0x3f3f3f;
int solve4(int l,int r)
{
if(l==r)
return a[l];
int mid = (l+r)>>1;
int left_sum = solve4(l,mid);
int right_sum = solve4(mid+1,r);
int sum1=0,sum2=0,s1=0,s2=0;
//閿熸枻鎷烽敓绔枻鎷烽敓锟?
for(int i =mid;i>=l;--i)
{
s1+=a[i];
sum1=max(sum1,s1);
}
for(int i =mid+1;i<=r;++i)
{
s2 +=a[i];
sum2 = max(sum2,s2);
}
int sum = sum1+sum2;
return max(max(left_sum,right_sum),sum);
}
int main()
{
int n;
cout<<"please input size"<<endl;
cin>>n;
cout<<"please input data"<<endl;
for(int i =1;i<=n;++i)
{
cin>>a[i];
}
int ans = solve4(1,n);
cout<<ans<<endl;
system("pause");
return 0;
}
4.动态规划 思路:这已经是可以用动态规划思想去考虑的最简单的问题了, 每一步的决策无非就是,是否继续把下一个元素加入当前的子段. 动态规划大显身手。我们开一个数组dp[] , 记录dp[i]表示以a[i]结尾的 全部子段中 最大的那个的 和。 这样我们就可以根据它dp[i] 的正负,去考虑是否把下一个元素加入到当前的子段。 如果dp[i] 是负数,那么我们为什不从a[i+1]新维护一个子段呢? 如果dp[i] 是正数,那么显然可以继续把a[i+1] 加入到当前的子段。 最后我们只需要找出所有最大子段中,最大的那个。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],b[N], dp[N];;
int n ;
int ans ;
const int INF = 0x3f3f3f;
int main()
{
int n;
cout<<"please input size"<<endl;
cin>>n;
cout<<"please input data"<<endl;
for(int i =1;i<=n;++i)
{
cin>>a[i];
}
dp[1] = a[1];
int ans =0;
for(int i =2;i<=n;++i)
{
if(dp[i-1]>0)
dp[i] =dp[i-1] + a[i];
else
dp[i] = a[i];
ans = max(ans,dp[i]);
}
cout<<ans<<endl;
system("pause");
return 0;
}