本文主要是介绍HDU-1003-动规-最大子序列和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：给一个序列，求它的最大子序列和，该子序列的起点，终点。
O(n)的做法.-容易标记起点终点！思想也很简单。
只要前面的加起来为负数了，就开始新的一段子序列和的计算。
4 0 0 2 0 —— 2 1 3
6 2 7 -9 5 4 3 —— 12 1 6
4 0 0 -1 0 —— 0 1 1
7 -1 -2 -3 -2 -5 -1 -2 —— -1 1 1 全部为负数时！
6 -1 -2 -3 1 2 3 —— 6 4 6
----------------------------------------------------------------------------------
增加一组测试数据：
5 -3 -2 -1 -2 -3 —— -1 3 3
#include<iostream>
using namespace std;
int a[100010];
int i;
int N;
int max_start,max_end,start;
int count=1;
int maxSubSum(const int *a)
{
int sum,max;
sum=max=a[1]; //一定要初始化为第一个
start=max_start=max_end=1; //都初始化为第一个.
for(int j=2;j<=N;j++) //从第二个开始枚举
{
/*一旦前面和为负数，则从新的起点又开始算子序列和!*/
if(sum+a[j]<a[j])//(首先只有sum为负数才可能满足条件)然后分两种情况,一个a[j]>=0,或者a[j]<0;
{
sum=a[j]; //例：-2 -1 1 只有加到一个正数才会 不满足这个条件！
start=j; //把sum 与start又从新起点j开始
}
else
sum+=a[j]; //否则一直加
if(sum>max) //当大于max
{
max=sum; //记录下所需要的 最大值 ，起点，终点.
max_start=start;
max_end=j;
}
}
return max;
}
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>N;
for(i=1;i<=N;i++)
cin>>a[i];
cout<<"Case "<<count++<<":"<<endl;
cout<<maxSubSum(a);
if(T!=0)
cout<<" "<<max_start<<" "<<max_end<<endl<<endl;
else
cout<<" "<<max_start<<" "<<max_end<<endl;
}
return 0;
}
O(nlogn)二分的做法-没有记录起点，终点.(只是二分的模板，与题无关)
(参考他人)
long max3(long a, long b, long c)
{
if (a < b)
{
a = b;
}
if (a > c)
return a;
else
return c;
}
//递归法，复杂度是O(nlogn) 难以记录 起点，终点!!!!!!!!
long maxSumRec(int* a, int left, int right)
{
if (left == right)
{
if (a[left] > 0)
return a[left];
else
return 0;
}
int center = (left + right) / 2;
long maxLeftSum = maxSumRec(a, left, center);
long maxRightSum = maxSumRec(a, center+1, right);
//求出以左边对后一个数字结尾的序列最大值
long maxLeftBorderSum = 0, leftBorderSum = 0;
for (int i = center; i >= left; i--)
{
leftBorderSum += a[i];
if (leftBorderSum > maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}
//求出以右边对后一个数字结尾的序列最大值
long maxRightBorderSum = 0, rightBorderSum = 0;
for (int j = center+1; j <= right; j++)
{
rightBorderSum += a[j];
if (rightBorderSum > maxRightBorderSum)
maxRightBorderSum = rightBorderSum;
}
cout<<"左="<<left<<"右="<<right<<endl;
cout<<"max3="<<max3(maxLeftSum, maxRightSum,
maxLeftBorderSum + maxRightBorderSum)<<endl;
return max3(maxLeftSum, maxRightSum,
maxLeftBorderSum + maxRightBorderSum);
} 这篇关于HDU-1003-动规-最大子序列和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
