目录

hdoj 1003求解方法

暴力求解O(n^3)/O(n^2)(不推荐,很可能会超时)

分治法(比较复杂,掌握思想即可)

遍历求和法O(n)

dp动态规划(强推)

codeup2086的求解方法

dp求解


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;
}