手机微网站建设,网页跳转到别的网站,网站订制公司,百度建站官网求一个序列的最大子序列和#xff0c;这个可以有几种方法都可以去求解#xff0c;这里我提供两种方法给大家。 假如这个序列是{1#xff0c;-2#xff0c;3#xff0c;4}#xff0c;显然最大子序列和是7#xff0c;那么这个要怎么去计算呢#xff1f; 第一种方法就是顺…求一个序列的最大子序列和这个可以有几种方法都可以去求解这里我提供两种方法给大家。 假如这个序列是{1-234}显然最大子序列和是7那么这个要怎么去计算呢 第一种方法就是顺序求取可以先算一下只有一个元素的最大值是多少再算一下连续两个元素的最大值是多少再算一下连续三个元素的最大值是多少 直到n个元素全部都取完。用一个数组来保存连续一个连续两个连续n个的和的最大值代码如下。 #includeiostream
using namespace std;
const int N-1e62;
int main()
{int n;cin n;int a[n];for(int i0;in;i){cin a[i];}int b[n];for(int i0;in;i){b[i]N;for(int j0;jn-i;j){int sum0;for(int kj;kji;k){suma[k];}if(sumb[i]){b[i]sum;}}}int mb[0];for(int i1;in;i){if(mb[i]){mb[i];}}cout m;return 0;
} 为了提高效率可以用两个for就可以实现最大值不用数组表示用一个变量max1保存一下。 #includeiostream
const int N1e61;
using namespace std;
int main()
{int n;cin n;int a[n];for(int i0;in;i){cin a[i];}int max1-N;for(int i0;in;i){int sum0;for(int ji;jn;j){suma[j];if(max1sum){max1sum;}}}cout max1;return 0;
} 最后给大家提供一下最简单的方法用动态规划就可以做做动态规划最重要的就是要找到状态转移方程这个问题的状态转移方程就是 dp[i]a[i]dp[i-1]或者是dp[i]a[i],代码如下 #includeiostream
#includealgorithm
const int N1e6;
using namespace std;
int main()
{int n;cin n;int a[n];int dp[n];for(int i0;in;i){cin a[i];dp[i]a[i];}int max1-N;for(int i1;in;i){dp[i]max(dp[i-1]a[i],a[i]);if(max1dp[i]){max1dp[i];}}cout max1;return 0;
}这个只用了一个for就可以实现了效率相比前面几个都提高了不少。转载于:https://www.cnblogs.com/sddr/p/10725102.html
