本文主要是介绍NYoj 44 子串和[经典动态规划2],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
/*NYoj 44 子串和经典的动态规划(就且成之为经典动态规划2)
*/
#include<iostream>
#define max(a,b) a>b?a:b
using namespace std;
int a[1000005],dp[1000005];//dp存储的是当前数值最优和.也就是最优解.
int MAX(int n)
{dp[1]=a[1];int Max=dp[1];for(int i=2;i<=n;i++){dp[i]=max(dp[i-1]+a[i],a[i]);Max=max(dp[i],Max);}return Max;
}
int main()
{int T;cin>>T;while(T--){int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];cout<<MAX(n)<<endl;}
}
这篇关于NYoj 44 子串和[经典动态规划2]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!