目录
hdoj 1003求解方法
-
暴力求解O(n^3)/O(n^2)(不推荐，很可能会超时）
思路 ：两层for循环，第一层i，第二层j，想办法计算i～j之间的和，再判断条件求解
https://blog.csdn.net/ten_sory/article/details/79776473
具体可参加此博客
-
分治法（比较复杂，掌握思想即可）
（摘自 LB_莫贺延碛的博客）
假设寻找的子数组A[low...high]为最大子数组，使用分支策略，意味着我们需要将原数组分为两个规模近似相同的子数组，那么我们可以找到数组a的中间位置mid
则数组A的位置可能有三种情况：
1.完全位于子数组a[low...mid] 中
2.完全位于子数组a[mid + 1... high]中
3.跨过中点
其中前两种情况我们直接使用递归即可，至于第三种情况，可以用这种策略，从中点开始，向左遍历数组求出最大的和 ，然后在从中点向右遍历，求出最大的和
之后两者相加，即获得过中点 和最大的子数组
代码(注意输出格式)
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <memory.h>
using namespace std;
const int maxn = 100000 + 10;
const int mini = -100000000;
int num[maxn];
//int memo[maxn][maxn];
int find_cross_subarray(int low,int high,int & cross_low,int & cross_high)// low_max 为过中点 到达最左边的下标，high_max 为过中点 到达最右边的下标
{
int mid = (low + high) / 2;
int res = 0;
int left_sum = mini;
for (int i = mid; i >= low; i--)
{
res += num[i];
if (res >= left_sum) //输出第一个 满足要求的数组 所以要尽量向左边靠拢
{
left_sum = res;
cross_low = i;
}
}//for int i
res = 0;
int right_sum = mini;
for (int i = mid + 1; i <= high; i++)
{
res += num[i];
if (res > right_sum)
{
right_sum = res;
cross_high = i;
}
}
return right_sum + left_sum;
}
int find_max_subarray(int low, int high,int & max_low,int & max_high) //max_low max_high为最终答案的左右下标
{
if (high == low)
{
max_low = max_high = low;
return num[high];
}
int mid = (low + high) / 2;
int left_low, left_high, left_sum;
int right_low, right_high, right_sum;
int cross_low, cross_high, cross_sum;
left_sum = find_max_subarray(low, mid,left_low,left_high);
right_sum = find_max_subarray(mid + 1, high,right_low,right_high);
cross_sum = find_cross_subarray(low, high, cross_low, cross_high);
if (left_sum >= cross_sum && left_sum >= right_sum)
{
max_low = left_low;
max_high = left_high;
return left_sum;
}
if (cross_sum >= left_sum && cross_sum >= right_sum)
{
max_low = cross_low;
max_high = cross_high;
return cross_sum;
}
max_low = right_low;
max_high = right_high;
return right_sum;
}
int main()
{
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
int casenum, length,seq = 0;
cin >> casenum;
while (casenum--)
{
if (seq != 0)
cout << endl;
cin >> length;
for (int i = 0; i < length; i++)
cin >> num[i];
int max_low, max_high, res;
res = find_max_subarray(0, length - 1, max_low, max_high);
cout << "Case " << ++seq << ":" << endl;
cout << res << " " << max_low + 1<< " " << max_high + 1<<endl;
}
return 0;
}
-
遍历求和法O(n)
思路：边遍历边累加,sum+=a[i],更新最大的sum值，当sum的值小于0 ，sum+a[i+1]<=a[i+1],则没有必要再曾长该子序列
则重新开始新的子序列
参考代码（来自博主 echo_hello）
#include<iostream>
using namespace std;
int main()
{
int T;
cin >> T;
int t = 0;
while(T--)
{
t ++;
int n, i, j;
cin >> n;
int *a = new int[n];
for(i=0;i<n;i++)
cin >> a[i];
int maxsum = -9999;
int sum = 0;
int startMax = 0, endMax = -1;
int startTemp = 0, endTemp = -1;
for(i=0;i<n;i++)
{
sum+=a[i];
endTemp ++;
if(sum>maxsum)
{
maxsum = sum;
startMax = startTemp;
endMax = endTemp;
}
if(sum<0)
{
sum = 0;
startTemp = i+1;
endTemp = i;
}
}
cout << "Case " << t << ":" << endl;
cout << maxsum << " " << startMax+1 << " " << endMax+1 << endl;
if(T>0)
cout << endl;
delete []a;
}
return 0;
}
-
dp动态规划（强推）
状态转移方程dp[i]=max(dp[i-1]+a[i],a[i]),和遍历求和思想相同
以a[i]为目标，判断它加上前面的子序列的和还没有自己本身大的话，那么新的最大子连续序列中的元素即a[i]
ac代码：（注意要初始化begin和end的值）
刚学dp的时候参考的网上的代码：
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#define maxn 100005
using namespace std;
int a[maxn],dp[maxn];
int main()
{
int k,ans,i,num=1,t;
scanf("%d",&t);
while(t--)
{
int begin=0,end=0;
memset(dp,0,sizeof(dp));
scanf("%d",&k);
for(i=0;i<k;i++)
{
scanf("%d", &a[i]);
}
dp[0]=a[0];
ans=dp[0];//ans用于更新最大的和
for(i=1;i<k;i++)
{
dp[i]=max(dp[i-1]+a[i],a[i]);//状态转移方程
if(dp[i]>ans)//直接在循环内更新ans的值，就不用再sort或者遍历寻找最大值了
{
ans=dp[i];
end=i;
}
}
int res=0;
for(i=end;i>=0;i--)
{
res+=a[i];
if(res==ans)
begin=i;
}
printf("Case %d:\n",num++);
printf("%d %d %d\n",ans,begin+1,end+1);
if(t!=0)
printf("\n");
}
return 0;
} 学了一段时间算法之后自己写的代码：
用f[]记录max sum子序列的起始位置
#include <bits/stdc++.h>
#define maxn 1000005
#define inf 2147483648
using namespace std;
typedef long long ll;
int f[maxn],dp[maxn],a[maxn];
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
int t,num=1,n;
scanf("%d",&t);
while(t--)
{
memset(dp,0,sizeof(dp));
if(num!=1) printf("\n");
printf("Case %d:\n",num++);
ll sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
f[1]=1;dp[1]=a[1];
int msum=a[1],k=1;
for(int i=2;i<=n;i++)
{
if(dp[i-1]+a[i]>=a[i])
{
f[i]=f[i-1];
dp[i]=dp[i-1]+a[i];
}
else{
f[i]=i;
dp[i]=a[i];
}
//cout<<dp[i]<<endl;
if(dp[i]>msum)
{
k = i;
msum=dp[i];
}
}
printf("%d %d %d\n",dp[k],f[k],k);
}
return 0;
} codeup2086的求解方法
-
dp求解
ac代码：
和hdoj1003同样的方法，也可以用f[]记录子序列起始的位置，只需对下面的代码做一点修改即可，就不再单独贴代码了。
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#define maxn 100000
using namespace std;
int a[maxn],dp[maxn];
int main()
{
int k,ans,begin,end,i;
while(scanf("%d",&k) && k!=0)
{
bool flag=true;
memset(dp,0,sizeof(dp));
for(i=0;i<k;i++)
{
scanf("%d", &a[i]);
if(a[i]>0)
flag=false;
}
if(flag)//k个元素全为负数
{
printf("%d %d %d\n",0,a[0],a[k-1]);
continue;
}
dp[0]=a[0];
ans=dp[0];//ans用于更新最大的和
for(i=1;i<k;i++)
{
dp[i]=max(dp[i-1]+a[i],a[i]);//状态转移方程
if(dp[i]>ans)
{
ans=dp[i];
end=i;
}
}
int res=0;
for(i=end;i>=0;i--)
{
res+=a[i];
if(res==ans)
begin=i;
}
//printf("%d %d %d\n",ans,begin+1,end+1);
printf("%d %d %d\n",ans,a[begin],a[end]);
}
return 0;
}
京公网安备 11010502036488号