问题描述：
输入一组整数，求出这组数字子序列和中最大值。也就是只要求出最大子序列的和，不必求出最大的那个序列。例如：
序列：-2 11 -4 13 -5 -2，则最大子序列和为20。
序列：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，则最大子序列和为16。
算法一：
//穷举法，复杂度O(n^3)
long maxSubSum1(const vector<int>& a)
{
long maxSum = 0;
for (int i = 0; i < a.size(); i++)
{
for (int j = i; j < a.size(); j++)
{
long thisSum = 0;
for (int k = i; k <= j; k++)
{
thisSum += a[k];
}
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
这是一个O(N^3) 的算法，算法本身很容易理解，而且很直观的感觉做了很多无用操作。例如：i = 0, j = 3时，会计算a[0] + a[1] +…+ a[3]；而当i = 0, j = 4时候又会计算a[0] + a[1] +…a[4]。
算法二：
通过撤出一个for循环来避免三次时间。
//也是穷举法，不过减去了上面的一些不必要操作O(n^2)
long maxSubSum2(const vector<int>& a)
{
long maxSum = 0;
for (int i = 0; i < a.size(); i++)
{
long thisSum = 0;
for (int j = i; j < a.size(); j++)
{
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
这是一个非常直观的穷举法（比上面的分析还有简单些），而且没有多余重复的操作，复杂度为O(N^2) 。其中，thisSum表示a[i] + a[i+1] + … + a[j-1]。
算法三：
对这个问题，有一个相对复杂的O(NlogN)的解法，就是使用递归。如果要是求出序列的位置的话，这将是最好的算法了（因为我们后面还会有个O(N)的算法，但是不能求出最大子序列的位置）。该方法我们采用“分治策略”（divide-and-conquer）。
在我们例子中，最大子序列可能在三个地方出现，或者在左半部，或者在右半部，或者跨越输入数据的中部而占据左右两部分。前两种情况递归求解，第三种情况的最大和可以通过求出前半部分最大和（包含前半部分最后一个元素）以及后半部分最大和（包含后半部分的第一个元素）相加而得到。
//递归法，复杂度是O(nlogn)
long maxSumRec(const vector<int>& a, int left, int right)
{
if (left == right)
{
if (a[left] > 0)
return a[left];
else
return 0;
}
int center = (left + right) / 2;
long maxLeftSum = maxSumRec(a, left, center);
long maxRightSum = maxSumRec(a, center+1, right);
//求出以左边对后一个数字结尾的序列最大值
long maxLeftBorderSum = 0, leftBorderSum = 0;
for (int i = center; i >= left; i--)
{
leftBorderSum += a[i];
if (leftBorderSum > maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}
//求出以右边对后一个数字结尾的序列最大值
long maxRightBorderSum = 0, rightBorderSum = 0;
for (int j = center+1; j <= right; j++)
{
rightBorderSum += a[j];
if (rightBorderSum > maxRightBorderSum)
maxRightBorderSum = rightBorderSum;
}
return max3(maxLeftSum, maxRightSum,
maxLeftBorderSum + maxRightBorderSum);
}
long maxSubSum3(const vector<int>& a)
{
return maxSumRec(a, 0, a.size()-1);
}
另外max3(long,long,long)表示求三个long中的最大值：
//求出三个long中的最大值
long max3(long a, long b, long c)
{
if (a < b)
{
a = b;
}
if (a > c)
return a;
else
return c;
}
对这个算法进行分析：
T(1) = 1
T(N) = 2T(N/2) + O(N)
最后得出算法的复杂度为：O(NlogN) 。
算法四：
下面介绍一个线性的算法，这个算法是许多聪明算法的典型：运行时间是明显的，但是正确性则很不明显（不容易理解）。
//线性的算法O(N)
long maxSubSum4(const vector<int>& a)
{
long maxSum = 0, thisSum = 0;
for (int j = 0; j < a.size(); j++)
{
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
else if (thisSum < 0)
thisSum = 0;
}
return maxSum;
}
很容易理解时间界O(N) 是正确的，但是要是弄明白为什么正确就比较费力了。其实这个是算法二的一个改进。分析的时候也是i代表当前序列的起点，j代表当前序列的终点。如果我们不需要知道最佳子序列的位置，那么i就可以优化掉。
重点的一个思想是：如果a[i]是负数那么它不可能代表最有序列的起点，因为任何包含a[i]的作为起点的子序列都可以通过用a[i+1]作为起点来改进。类似的有，任何的负的子序列不可能是最优子序列的前缀。例如说，循环中我们检测到从a[i]到a[j]的子序列是负数，那么我们就可以推进i。关键的结论是我们不仅可以把i推进到i+1，而且我们实际可以把它一直推进到j+1。
举例来说，令p是i+1到j之间的任何一个下标，由于前面假设了a[i]+…+a[j]是负数，则开始于下标p的任意子序列都不会大于在下标i并且包含从a[i]到a[p-1]的子序列对应的子序列（j是使得从下标i开始成为负数的第一个下标）。因此，把i推进到j+1是安全的，不会错过最优解。注意的是：虽然，如果有以a[j]结尾的某序列和是负数就表明了这个序列中的任何一个数不可能是与a[j]后面的数形成的最大子序列的开头，但是并不表明a[j]前面的某个序列就不是最大序列，也就是说不能确定最大子序列在a[j]前还是a[j]后，即最大子序列位置不能求出。但是能确保maxSum的值是当前最大的子序列和。这个算法还有一个有点就是，它只对数据进行一次扫描，一旦a[j]被读入处理就不需要再记忆。它是一个联机算法。
联机算法：在任意时刻算法都能够对它已读入的数据给出当前数据的解。
常量空间线性时间的联机算法几乎是完美的算法。
附录：
程序测试：
先通过文件读写函数产生一组随机数并且读入到一个vector<int>中：
//COUNT和MAX_NUM分别表示随机数个数和最大值
const long COUNT = 1000;
const int MAX_NUM = 200;
//读文件
bool readFile(vector<int>& input, string fileName)
{
ifstream infile(fileName.c_str());
if (!infile)
return false;
int s;
while(infile>>s)
{
input.push_back(s);
}
return true;
}
//写大量随机测试数据
bool writeTestData(string fileName)
{
ofstream outfile(fileName.c_str());
if (!outfile)
return false;
srand((unsigned)time(NULL));
for (int i = 0; i < COUNT; i++)
{
if (rand() % 2 == 0)
outfile << rand() % MAX_NUM << '\n';
else
outfile << ~(rand() % MAX_NUM) << '\n';
}
return true;
}
测试可得：
当COUNT = 1000的时候maxSubSum1()要等10s，后三个很快。
当COUNT = 10000的时候maxSubSum2()要等8s，后两个很快。
当COUNT = 1000000的时候maxSubSum3()要等10s，maxSubSum4()要等4s。
其实当COUNT = 1000000这个时候但是作文件读写就要很耗时了，光是in.txt就达到了4.7MB了。
而COUNT = 10000000的时候光是文件读写就要半分钟，in.txt达到了47.2MB，这时候再做maxSubSum3()和maxSubSum4()的比较，maxSubSum4()需要56s，而maxSubSum3()这时候需要85s（包括了读文件的时间）。可见数据量比较大的情况下O(NlogN)的递归算法也是可行的，并不比O(N)低很多。尤其在要求出最大子序列位置的情况下，分治递归算法体现了强大的威力。
程序源码：
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
//COUNT和MAX_NUM分别表示随机数个数和最大值
const long COUNT = 10000;
const int MAX_NUM = 200;
//读文件
bool readFile(vector<int>& input, string fileName)
{
ifstream infile(fileName.c_str());
if (!infile)
return false;
int s;
while(infile>>s)
{
input.push_back(s);
}
return true;
}
//写大量随机测试数据
bool writeTestData(string fileName)
{
ofstream outfile(fileName.c_str());
if (!outfile)
return false;
srand((unsigned)time(NULL));
for (int i = 0; i < COUNT; i++)
{
if (rand() % 2 == 0)
outfile << rand() % MAX_NUM << '\n';
else
outfile << ~(rand() % MAX_NUM) << '\n';
}
return true;
}
//穷举法
long maxSubSum1(const vector<int>& a)
{
long maxSum = 0;
for (int i = 0; i < a.size(); i++)
{
for (int j = i; j < a.size(); j++)
{
long thisSum = 0;
for (int k = i; k <= j; k++)
{
thisSum += a[k];
}
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
//也是穷举法，不过减去了上面的一些不必要操作O(n^2)
long maxSubSum2(const vector<int>& a)
{
long maxSum = 0;
for (int i = 0; i < a.size(); i++)
{
long thisSum = 0;
for (int j = i; j < a.size(); j++)
{
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
//递归法，复杂度是O(nlogn)
long max3(long a, long b, long c)
{
if (a < b)
{
a = b;
}
if (a > c)
return a;
else
return c;
}
long maxSumRec(const vector<int>& a, int left, int right)
{
if (left == right)
{
if (a[left] > 0)
return a[left];
else
return 0;
}
int center = (left + right) / 2;
long maxLeftSum = maxSumRec(a, left, center);
long maxRightSum = maxSumRec(a, center+1, right);
//求出以左边对后一个数字结尾的序列最大值
long maxLeftBorderSum = 0, leftBorderSum = 0;
for (int i = center; i >= left; i--)
{
leftBorderSum += a[i];
if (leftBorderSum > maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}
//求出以右边对后一个数字结尾的序列最大值
long maxRightBorderSum = 0, rightBorderSum = 0;
for (int j = center+1; j <= right; j++)
{
rightBorderSum += a[j];
if (rightBorderSum > maxRightBorderSum)
maxRightBorderSum = rightBorderSum;
}
return max3(maxLeftSum, maxRightSum,
maxLeftBorderSum + maxRightBorderSum);
}
long maxSubSum3(const vector<int>& a)
{
return maxSumRec(a, 0, a.size()-1);
}
//线性的算法O(N)
long maxSubSum4(const vector<int>& a)
{
long maxSum = 0, thisSum = 0;
for (int j = 0; j < a.size(); j++)
{
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
else if (thisSum < 0)
thisSum = 0;
}
return maxSum;
}
int main ()
{
vector<int> input;
/**
if (!writeTestData("in.txt"))
{
cout << "写文件错误" << endl;
}
*/
if (readFile(input, "in.txt"))
{
//cout << maxSubSum1(input) << endl;
//cout << maxSubSum2(input) << endl;
cout << maxSubSum3(input) << endl;
cout << maxSubSum4(input) << endl;
}
return 0;
}
转自：http://www.cnblogs.com/CCBB/archive/2009/04/25/1443455.html
相关推荐
内容概要：本文详细探讨了在Simulink环境中构建的风火水储联合调频系统中，储能系统的荷电状态（SOC）对区域控制偏差（ACE）的影响。文中通过具体案例和MATLAB代码展示了储能系统在不同SOC水平下的表现及其对系统稳定性的作用。同时，文章比较了储能单独调频与风火水储联合调频的效果，强调了储能系统在应对风电波动性和提高系统响应速度方面的重要作用。此外，作者提出了针对SOC变化率的参数整定方法以及多电源协同工作的优化策略，旨在减少ACE波动并确保系统稳定运行。 适合人群：从事电力系统调频研究的专业人士，尤其是熟悉Simulink仿真工具的研究人员和技术人员。 使用场景及目标：适用于希望深入了解储能系统在电力系统调频中作用的研究者和技术人员，目标是通过合理的SOC管理和多电源协同工作，优化调频效果，提高系统稳定性。 其他说明：文章提供了详细的MATLAB代码片段，帮助读者更好地理解和应用所讨论的概念。同时，文中提到的实际案例和仿真结果为理论分析提供了有力支持。
内容概要：本文深入探讨了欧姆龙PLC NJ系列中大型程序中结构化编程与面向对象编程的结合及其应用。首先介绍了结构化编程作为程序框架的基础，通过功能块（FB）实现清晰的程序结构和流程控制。接着阐述了面向对象编程的理念，将现实世界的对象映射到程序中，利用类的概念实现模块化和可扩展性。两者结合提高了程序的容错率，增强了程序的稳定性和可维护性。文中通过多个实际案例展示了如何在工业自动化领域中应用这两种编程方法，如电机控制、设备类的创建、异常处理机制、接口实现多态性、配方管理和报警处理等。 适合人群：从事工业自动化领域的工程师和技术人员，尤其是那些希望提升PLC编程技能的人群。 使用场景及目标：适用于需要优化PLC程序结构、提高程序可靠性和可维护性的场合。目标是帮助工程师掌握结构化编程和面向对象编程的技巧，从而写出更加高效、稳定的PLC程序。 其他说明：文章强调了在实际项目中灵活运用两种编程方法的重要性，并提醒读者注意实时性要求高的动作控制应采用结构化编程，而工艺逻辑和HMI交互则更适合面向对象编程。
matlab与聚类分析。根据我国历年职工人数（单位：万人），使用有序样品的fisher法聚类。
卡尔曼滤波生成航迹测量程序
内容概要：本文详细介绍了利用格子玻尔兹曼方法（LBM）对多孔电极浸润特性的模拟研究。首先阐述了LBM的基本原理，包括碰撞和迁移两个关键步骤，并提供了相应的Python伪代码。接着讨论了如何处理多孔介质中的固体边界，特别是通过随机算法生成孔隙结构以及结合CT扫描数据进行三维重构的方法。文中还探讨了表面张力、接触角等因素对浸润过程的影响，并给出了具体的数学表达式。此外，文章提到了并行计算的应用，如使用CUDA加速大规模网格计算，以提高模拟效率。最后，作者分享了一些实用技巧，如通过调整松弛时间和润湿性参数来优化模拟效果，并强调了LBM在处理复杂几何结构方面的优势。 适合人群：从事电池研发、材料科学领域的研究人员和技术人员，尤其是关注多孔电极浸润性和电解液扩散机制的人群。 使用场景及目标：适用于希望深入了解多孔电极内部流体动力学行为的研究者，旨在帮助他们更好地理解和预测电极材料的浸润特性，从而改进电池设计和性能。 其他说明：尽管LBM在处理多孔介质方面表现出色，但在某些极端条件下仍需引入额外的修正项。同时，参数的选择和边界条件的设定对最终结果有着重要影响，因此需要谨慎对待。
内容概要：本文详细介绍了在Zynq扩展口上使用FPGA和W5500实现TCP网络通信的过程。作者通过一系列实验和技术手段，解决了多个实际问题，最终实现了稳定的数据传输。主要内容包括：硬件搭建（SPI接口配置）、数据回环处理、压力测试及优化、多路复用扩展以及上位机测试脚本的编写。文中提供了大量Verilog代码片段，展示了如何通过状态机控制SPI通信、优化数据缓存管理、处理中断等问题。 适合人群：对FPGA开发和网络通信感兴趣的工程师，尤其是有一定Verilog编程基础的研发人员。 使用场景及目标：适用于需要在嵌入式系统中实现高效、稳定的TCP通信的应用场景。目标是帮助读者掌握FPGA与W5500结合进行网络通信的具体实现方法和技术细节。 其他说明：文章不仅提供了详细的代码实现，还分享了许多实践经验，如硬件连接注意事项、信号完整性问题的解决方案等。此外，作者还提到了未来的工作方向，如UDP组播和QoS优先级控制的实现。
python3.10以上 可安装pyside6（类似pyqt），具体安装操作步骤
内容概要：本文详细介绍了利用有限差分时域法(FDTD)进行可调谐石墨烯超材料吸收体的设计与仿真。文中解释了石墨烯超材料的基本结构（三层“三明治”结构）、关键参数（如化学势、周期、厚度等）及其对吸收性能的影响。同时展示了如何通过调整石墨烯的化学势来实现吸收峰的位置和强度的变化，以及如何优化结构参数以获得最佳的吸收效果。此外，还提供了具体的代码示例，帮助读者理解和重现相关实验结果。 适合人群：从事纳米光子学、超材料研究的专业人士，尤其是对石墨烯基超材料感兴趣的科研工作者和技术开发者。 使用场景及目标：适用于希望深入了解石墨烯超材料的工作原理及其潜在应用场景的研究人员；旨在探索新型可调谐光学器件的设计思路和发展方向。 其他说明：文中不仅分享了理论知识，还包括了许多实践经验，如避免常见错误、提高仿真相关效率的小技巧等。对于想要将研究成果应用于实际产品的团队来说，这些细节非常有价值。
随机生成2字，3字，4字，5字，6字，7字，8字，9字，10字的中文词组20个
内容概要：本文详细探讨了智能座舱域控设计的发展历程和技术趋势。首先介绍了智能座舱从被动式交互到主动式交互的技术演变，包括硬件和交互方式的进步。随后，文章重点讨论了智能座舱功能发展趋势，涵盖车载显示技术的多屏化、大屏化和高端化，以及SoC芯片的多核异构架构和算力融合，强调了其在智能座舱中的核心作用。此外，还阐述了电子电气架构从分布式向集成化的转型，分析了其面临的挑战和未来趋势。最后，基于当前智能座舱的发展需求，提出了一种基于双片龍鷹一号芯片的新域控平台设计方案，详细描述了其硬件设计实现方案，旨在提供高性能、高可靠性的智能座舱解决方案。 适合人群：汽车电子工程师、智能座舱研发人员及相关领域的技术人员。 使用场景及目标：①帮助读者理解智能座舱的技术发展历程及其未来发展方向；②为智能座舱域控平台的设计和开发提供参考和技术支持；③探讨电子电气架构的转型对汽车行业的影响及应对策略。 其他说明：文章结合实际案例和技术数据，深入浅出地解释了智能座舱的各项技术细节，不仅提供了理论指导，还具有较强的实践意义。通过对智能座舱域控平台的全面剖析，有助于推动智能座舱技术的创新发展，提升用户体验。
内容概要：本文详细介绍了多智能体协同编队控制的技术原理及其应用实例。首先通过生动形象的例子解释了编队控制的核心概念，如一致性算法、虚拟结构法和Leader-Follower模式。接着深入探讨了如何用Python实现基础的一致性控制，以及如何通过调整参数（如Kp、Ka）来优化编队效果。文中还讨论了实际工程中常见的问题，如通信延迟、避障策略和动态拓扑变化，并给出了相应的解决方案。最后，强调了参数调试的重要性，并分享了一些实用技巧，如预测补偿、力场融合算法和分布式控制策略。 适合人群：对多智能体系统、无人机编队控制感兴趣的科研人员、工程师和技术爱好者。 使用场景及目标：适用于希望深入了解多智能体协同编队控制理论并能够将其应用于实际项目的研究人员和开发者。目标是帮助读者掌握编队控制的关键技术和实现方法，提高系统的稳定性和可靠性。 其他说明：文章不仅提供了详细的理论讲解，还附有具体的代码示例，便于读者理解和实践。同时，作者结合自身经验分享了许多宝贵的调试技巧和注意事项，有助于读者在实际应用中少走弯路。
评估管线钢环焊缝质量及其对氢脆的敏感性.pptx
C盘清理bat脚本自动清理C盘垃圾文件
GBT21266-2007 辣椒及辣椒制品中辣椒素类物质测定及辣度表示方法
弹跳球 XNA 游戏项目。演示如何使用 C# 在 Visual Studio XNA 中构建类似 arkanoiddx-ball 的游戏。
内容概要：文章全面解析了宇树科技人形机器人的发展现状、技术实力、市场炒作现象及其应用前景和面临的挑战。宇树科技成立于2016年，凭借春晚舞台的惊艳亮相和社交媒体的热议迅速走红，其人形机器人具备先进的运动控制算法、传感器技术和仿生结构设计。然而，市场炒作现象如高价租赁、二手市场炒作和虚假宣传等影响了市场秩序。尽管存在炒作，人形机器人在工业、服务和家庭领域仍具广阔前景，但也面临技术升级、成本控制、安全性和政策监管等挑战。 适合人群：对机器人技术、人工智能以及科技发展趋势感兴趣的读者，包括科技爱好者、投资者和相关行业的从业者。 使用场景及目标：①帮助读者了解宇树科技人形机器人的技术特点和发展历程；②揭示市场炒作现象及其影响；③探讨人形机器人的应用前景和面临的挑战。 其他说明：文章强调了宇树科技人形机器人在技术上的突破和市场上的表现，同时也提醒读者关注市场炒作现象带来的风险，呼吁各方共同努力推动人形机器人产业健康发展。
msvcp140.dll丢失怎样修复
超透镜是一种将具有特殊电磁特性的纳米结构、按照一定方式进行排列的二维平面透镜，可实现对入射光振幅、相位、偏振等参量的灵活调控，在镜头模组、全息光学、AR/VR等方面具有重要应用，具有颠覆传统光学行业的潜力。 目前，超透镜解决方案的市场处于起步阶段，企业根据客户的具体需求和应用场景为其定制专用超透镜或超透镜产品。 根据QYResearch最新调研报告显示，预计2031年全球超透镜解决方案市场规模将达到29.26亿美元，未来几年年复合增长率CAGR为79.55%。 全球范围内，超透镜解决方案主要生产商包括Metalenz, Inc., Radiant Opto-Electronics (NIL Technology),迈塔兰斯、纳境科技、山河元景等，其中前五大厂商占有大约77.84%的市场份额。 目前，全球核心厂商主要分布在欧美和亚太地区。 就产品类型而言，目前红外超透镜解决方案是最主要的细分产品，占据大约96.76%的份额。 就产品类型而言，目前消费电子是最主要的需求来源，占据大约36.27%的份额。 主要驱动因素: 独特性能优势：超透镜解决方案具有更轻薄、成本更低、成像更好、更易集成、更高效及更易自由设计等优势。能以微米级厚度实现传统厘米级透镜功能，还可集多个光学元件功能于一身，大幅减小成像系统体积、重量，简化结构并优化性能。 技术创新推动：超透镜解决方案技术不断取得进步，设计技术和工艺水平持续提升，其性能和稳定性得以不断提高。制造工艺方面，电子束光刻等多种技术应用到超透镜解决方案生产中，推动超透镜解决方案向更高分辨率、更高产量、更大面积、更高性能的方向发展。 市场需求增长：消费电子、汽车电子、医疗、工业等众多领域快速发展，对高精度、高性能光学器件需求不断增加。如在手机摄像头中可缩小模组体积、提升成像分辨率和降低成本；在汽车电子领域能提高车载摄像头、激光雷达等传感器性能。
内容概要：本文详细介绍了基于MATLAB和优化工具Gurobi/Cplex实现的新能源并网电力市场调度模型。该模型通过IEEE30节点系统进行仿真，重点探讨了风电接入对传统火电调度的影响。文中展示了关键决策变量如机组启停状态、实时出力以及风电出力的定义方法，并深入解析了目标函数的设计，特别是总成本函数中燃料成本、启停成本、备用成本和弃风惩罚之间的权衡。此外，文章还讨论了直流潮流约束的作用，以及节点电价计算背后的经济学原理。最后，通过对不同情景的模拟实验，验证了模型的有效性和实用性。 适用人群：适用于从事电力系统研究、电力市场运营管理和新能源并网调度的专业人士和技术人员。 使用场景及目标：①帮助理解和掌握新能源并网对电力市场调度的具体影响；②为制定合理的电力市场规则和政策提供理论依据和技术支持；③指导实际电力系统的调度操作，提高系统运行效率和经济效益。 其他说明：文中提供的代码片段和具体实现细节有助于读者更好地理解模型的构造和求解过程。同时，强调了在实际应用中需要注意的问题，如弃风惩罚系数的选择、备用容量的配置等。
用Python开发的爬取二手车网站数据及其分析的程序，爬取的时候采用selenium驱动google浏览器进行数据的抓取，抓取的网页内容传入lxml模块的etree对象HTML方法通过xpath解析DOM树，不过二手车的关键数据比如二手车价格，汽车表显里程数字采用了字体文件加密。据的展示采用pyecharts，它是一个用于生成 Echarts 图表的类库。爬取的数据插入mysql数据库和分析数据读取mysql数据库表都是通过pymysql模块操作。