NYOJ 44 子串和 （经典的dp问题）

本文主要是介绍NYOJ 44 子串和 （经典的dp问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在《计算机算法设计与分析》看到过其它的解法，不过还是用dp效率最高

时间限制：5000 ms  |  内存限制：65535 KB

难度：3

• 描述

• 给定一整型数列{a₁,a₂...,a_n}，找出连续非空子串{a_x,a_x+1,...,a_y}，使得该子序列的和最大，其中，1<=x<=y<=n。

  • 输入

  • 第一行是一个整数N(N<=10)表示测试数据的组数）
    每组测试数据的第一行是一个整数n表示序列中共有n个整数，随后的一行里有n个整数I(-100=<I<=100)，表示数列中的所有元素。(0<n<=1000000)

  • 输出

  • 对于每组测试数据输出和最大的连续子串的和。

  • 样例输入

  • 1
    5
    1 2 -1 3 -2

  • 样例输出

  • 5

#include <iostream>
#include <climits>
#include <stdio.h>
#include <vector>using namespace std;int MaxSum(const vector<int> &v,const int &m)
{int i,lmax,tmax;lmax=-INT_MAX;tmax=0;for(i=0;i<m;i++){tmax+=v[i];if(tmax>lmax)lmax=tmax;if(tmax<0)tmax=0;}return lmax;
}int main()
{int n,m,i;scanf("%d",&n);while(n--){scanf("%d",&m);vector<int> v(m);for(i=0;i<m;i++)scanf("%d",&v[i]);printf("%d\n",MaxSum(v,m));}return 0;
}

低效算法

#include <iostream>
#include <stdio.h>
#include <vector>using namespace std;int MaxSum(const vector<int> &v,const int &m)
{int i,j,lmax,tmax;lmax=0;for(i=0;i<m;i++){tmax=0;for(j=i;j<m;j++){tmax+=v[j];if(tmax>lmax)lmax=tmax;}}return lmax;
}int main()
{int n,m,i,num;scanf("%d",&n);while(n--){scanf("%d",&m);vector<int> v(m);for(i=0;i<m;i++){scanf("%d",&num);v[i]=num;}printf("%d\n",MaxSum(v,m));}return 0;
}

标程

#include <iostream>
#include <climits>
#include <cstdio>using namespace std;int arrMax[1000000]={0};int main()
{int n,m,i,max;scanf("%d",&n);while(n--){max=-INT_MAX;scanf("%d",&m);for(i=1;i<=m;i++){scanf("%d",&arrMax[i]);if(arrMax[i-1]>0)arrMax[i]+=arrMax[i-1];if(arrMax[i]>max)max=arrMax[i];}printf("%d\n",max);}return 0;
}

这篇关于NYOJ 44 子串和 （经典的dp问题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---