给定由 n 个整数（可能为负整数）组成的序列，求解其连续的最大字段和。当所有数都是负整数时，最大字段和是 0 .
如：a[] = {-2, 11, -4, 13, -5, -2}时， max = 11 + (-4) + 13 = 20.
将所给序列a[1:n] 分成a[1:n/2] 和 a[n/2 + 1 : n]两个部分，则最大值有一下三种情况：
对应前两种情况利用递归可以直接求出，而第三种情况可以从中间部分向两边蔓延（直到找到的数是负数为止）
时间复杂度为：nlogn
int maxSubSum(int *a, int left, int right) {
if (left == right) {
return a[left] < 0 ? 0 : a[left];
}
int centor = (left + right) / 2;
int leftSum = maxSubSum(a, left, centor);
int rightSum = maxSubSum(a, centor + 1, right);
int s1 = 0;
int lefts =0;
for (int i = centor; i >= left; i--) {
// 从中点向左找最大字段和
lefts += a[i];
if (lefts > s1) {
s1 = lefts;
}
}
int s2 = 0;
int rights = 0;
for (int i = centor + 1; i <= right; i++) {
//从中点向右找最大字段和
rights += a[i];
if (rights > s1) {
s1 = rights;
}
}
int sum = s0 + s1; // 第三种情况的最大子段和
sum = max(sum, leftSum); // 求解三种情况的最大值
sum = max(sum, rightSum);
return sum;
}
int maxSum(int *a, int n) {
return sumSubSum(a, 1, n); // 可以根据数组a自行调整
}
用一个数组b[]，b[j]表示以从位置 j 开始向前找一段的最大子段和，当b[j - 1] > 0时， b[j] = b[j-1] + a[j] , 当 b[j-1] 小于0的时候，b[j] = a[j]，即动态方程为b[j] = max( b[j - 1] + a[j], a[j]). 最后结果为 数组b的最大值
算法实现：
int maxSum(int *a, n) {
int sum = 0, b = 0;
for (int i = 0; i < n; i++) {
if (b > 0) {
b += a[i]
} else {
b = a[i];
}
if (b > sum) {
sum = b; // 存储之前计算的最大值
}
}
return sum;
}
文章浏览阅读4.7w次，点赞8次，收藏91次。由于这几天项目需要实时显示监控的视频，所以网上翻阅了很多资料，这里写下我从0到1的过程。本篇博客参考了 ：https://blog.csdn.net/liona_koukou/article/details/84025449博客，也非常感谢此博主对我一些问题的回复和帮助。写在最前：推荐大家一个测试视频流是否可以播放的测试工具：点击下载，建议大家在视频流无法播放时先用此工具测试下源..._vue-video-player播放实时视频
文章浏览阅读3k次。运维监控的重要性：==========================运维工作中比较重要的一个部分，可以说，一切线上系统都需要 监控。考虑几个话题：1、什么是监控？ ============================一种实时获取某种对象的 状态、信息 的手段。人类社会中，监控无处不在。 手段各式各样。在我们的运维工作中，监控的主要对象是 和企业 业务相关的各种 服务器硬件状..._什么是运维监控系统
文章浏览阅读4.3k次。我的应用程序创建一个TCP连接，这是正常工作。 但在一个网络服务器有很多IP说TCP连接错误115正在进行操作原因是什么？174.XXX54.xxx 这样当调用TCP连接(非60秒超时阻塞) 到IP 174.X.X.X总是成功。 但是TCP连接到ip 54.x.x.x的同一台服务器正在失败(大部分时间)，正在进行测量操作。能否请您给我解释一下什么是错误号115OS可能的原因是：Linux的我的TC..._tcp error 115
文章浏览阅读367次。·基本sql语句1、DDL数据库定义语言主要用于建立、修改、删除数据库对象（表），不需要事务的参与CREATE:创建表CREATE TABLE emp(id NUMBER(10),name VARCHAR2(20),gender CHAR(1),birth DATE,salary NUMBER(6,2));DESC :查询表结构DESC emp;RENA..._oracle数据库的oracle_home查询
文章浏览阅读482次。1.字符串(string) strlen 意义：获得字符串长度，以'\0'为结束标志。(长度不包含'\0');注意：函数返回值是size_t(unsinged int)模拟实现strlen：size_t my_strlen(char *str){ size_t count = 0; while (*str) { count++; str++; } return count;}int main(){ char arr2[] = "abcdef".._string memory
文章浏览阅读3k次。作为一个光学专业的学生，光的干涉是一个基础知识点。所以尝试着做了个安卓app，来模拟球面波的干涉现象，效果如下：通过改变参数，可以观察到不同的现象。先从介绍干涉实验原理开始，首先如下图所示：点光源s1和s2在同一直线上，设为x轴，观察屏在距离它们为D的位置上，观察屏平行于y-z平面，在观察屏上各点光强不同，即存在干涉现象。s1和s2发射球面波，所以在空间任意一点上的光强与距_波的干涉模拟器
文章浏览阅读91次。前言：又是一年总结时啊。本来总结打算前几天就该写的。但由于一直在忙最后的期末考试，今天终于考完了。现在终于有时间来对这一年进行总一下了。刚开始的时候想了半天不知道该用什么题目好。想了想，今年的博客一直围绕着“java程序员由笨鸟到菜鸟”的专题来写的。现在想想。经过一年的洗礼，差不多由一个没有思想，没有想法的笨鸟变成会敲两行代码的菜鸟了。所以有了现在的“java菜鸟程序员2012总结”题..._程序员感恩总结
文章浏览阅读89次。简单谈谈php浮点数精确运算bc是Binary Calculator的缩写。bc*函数的参数都是操作数加上一个可选的 [int scale]，比如string bcadd(string $left_operand, string $right_operand[, int $scale])，如果scale没有提供，就用bcscale的缺省值。这里大数直接用一个由0-9组成的string表示，计算结果..._php中获得浮点数的二进制表示
文章浏览阅读2.6k次。我是否可以switch发表声明,决定返回什么？例如,我想根据我的想法返回不同的东西return.Eclipse给了我一个错误,希望我把switch声明放在外面switch.不确定要搜索什么,如果这是重复,请对不起.这是我的代码:public String wordBank() { //Error here saying: "This method must return a type of str..._case 里面放return
文章浏览阅读113次。介绍由于Python对XML读写有多种库，本文以xml.etree import ElementTree为例。解析from xml.etree import ElementTree as ET############ 解析方式一 ############# 打开文件，读取XML内容str_xml = open('xo.xml', 'r').read()# 利用ElementTree.XML将字符串..._python xml 多条目 读写
文章浏览阅读440次。计算机二级C语言程序设计试题及答案尽管C语言提供了许多低级处理的功能，但仍然保持着良好跨平台的特性，以一个标准规格写出的C语言程序可在许多电脑平台上进行编译，甚至包含一些嵌入式处理器(单片机或称MCU)以及超级电脑等作业平台。今天，小编特意为大家推荐计算机二级C语言程序设计试题及答案，一起看看吧！1.C语言中，关系表达式和逻辑表达式的值是( B ) 。A、0B、 0或1C、 1D、‘T’或’F’2..._设整型变量 x=2,则执行下列语句后,浮点型变量丫 的值不为 0.5 的
文章浏览阅读360次。1 FPGA开发必备1、 FPGA理论知识。2 、 FPGA开发语言。3 、 FPGA代码编辑器。4 、 FPGA仿真软件。5 、 FPGA开发软件。6 、 FPGA调试软件。7 、 FPGA板卡。8 、 FPGA硬件测试。9 、 FPGA文档编写。10 、FPGA时序收敛。2 结束语如果遇到问题，可以一起沟通讨论，邮箱：[email protected]。..._fpga必背