#include <iostream>
#include <stdio.h>
using namespace std;
int n;
int a[100000];
int maxsum(){ // 最优方法
int res =0,b=0;
for(int i=0;i<n;i++){ //前面的子段和都为负数
if(b>0) b+=a[i];
else b=a[i]; //重新计算字段和
if(b>res) res=b; // 取最大值
}
return res;
}
int maxsum2(){ //常见方法
int res=0;
for(int i=0;i<n;i++)
{
int b=0;
for(int j=i;j<=n;j++) // 从当前位开始向后计算各字段和
{
b=b+a[j];
if(res<b) // 取最大值
res=b;
}
}
return res;
}
int main()
{
freopen("in.txt","r",stdin);
cin>> n ;
for(int i=0;i<n;i++)
cin >>a[i];
cout << maxsum()<< endl;
return 0;
}
相关推荐
C++的作业,最大字段和问题 分治法,程序直接用dev就能运行。求一个序列的最大子段和即最大连续子序列之和。例如序列[4, -3, 5, -2, -1, 2, 6, -2]
最大字段和的分治解法 最大字段和的分治解法
用c++实现动态规划求最大字段和,直接运行,很好的
求一个n个数的最大字段和问题,以及对其进行输出。基本的贪心算法问题。常用与研究生算法课程。
Java实现算法最大字段和
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
用动态规划法求解最大字段和问题,DEV C++环境运行,测试可用可进行多组数据测试
对DP问题中的最大m字段和问题进行ppt演示讲解
最大字段和问题:分别用蛮力法 分治法 动态规划法去实现的!是我交给老师的实验报告!!
最大字段和-Kadane算法 最大字段和-Kadane算法 最大字段和-Kadane算法 最大字段和-Kadane算法 最大字段和-Kadane算法 最大字段和-Kadane算法 最大字段和-Kadane算法 最大字段和-Kadane算法 最大字段和-Kadane算法
/*蛮力法 n^2 对于数组a[n],其连续的子段有 以a[0]开始的 , { a[0] }, { a[0],a[1] },{ a[0],a[1],a[2] }.....共n 个 以a[1]开始的, { a[1] }, { a[1],a[2] },{ a[1],a[2],a[3] }........ ... 以a[n]开始的,{ a[n] }...
算法设计 根据书本算法 自己写了部分代码 求最大字段和 仅供参考
求最大字段的三种方法——_动态规划_蛮力_分治算法
最大子段和问题,可参考《算法设计...程序应该给出良好的用户界面,输出最大子段相关信息,包括:最大字段和、起始下标、终止下标等。 扩展:可以求解数组中任意区间段内的最大子段和及该子段和的起始下标和终止下标。
本文是mysql 数据库 问题一 将表一的数据导入表二...在表中插入数据时,某一字段取数据库中该字段的最大值,并+1,这个问题很多人都说用存储过程什么的解决,其实使用insert 和 select 结合就可以很好的解决这个问题啊
m个子段的总和最最大m子段和问题:给定由n个整数(可能为负)组成的序列a1、a2、a3...,an,以及一个正整数m,要求确定序列的m个不相交子段,使这大!
关于字段增强关于字段增强关于字段增强关于字段增强关于字段增强关于字段增强
欧几里得、批处理作业、素数环、天平问题、图着色、折半查找、最大字段和、最长递增子序列
S4 HANA MSEG 增加自定义字段和MSEG扩展字段.docx
最近对问题 最大子段和(分治法) 最长公共子序列问题 最大子段和(动态规划)