最大子序列和算法分析
问题描述:给定n个整数序列{a1,a2,...,an},求函数f(i,j)=max{0,Σak}(k:连续的从i取到j);
问题即为求已连续子列和的最大值,若果最大值为负数则取0,比如8个数序列{-1,2,-3,4,-2,5,-8,3},那摩最大子序列和为4+(-2)+5=7.
这个问题有四种不同复杂度的算法,算法1到四的时间复杂度是O(n3),O(n2),O(nlogn),O(n);
算法一:
最直接的方法是穷举法,列出所有的情况,我们可以设定子序列的左端i和右端j,再利用一层计算出a[i]到a[j]的和.
//最大子列和穷举法
#include
using namespace std;
int Find_Maxsun(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int Find_Maxsun(int*a, int n){
int MaxSun = 0, i, j, k;
int NowSum;
for (i = 0; i for (j = 0; j NowSum = 0;
for (k = i; k NowSum += a[k]; /*从a[i]到a[j]的子序列*/
if (NowSum>MaxSun)
MaxSun = NowSum; /*更新结果*/
}
return MaxSun;
}
很显然,暴力法使用啦3重for循环,算法时间复杂度为O(n3),这当然也是一个最笨的算法,但数据难非常庞大时候,哪怕是要算到死的节奏,我们可以清楚看到第三层for循环,
j每加一次,子列和都要重头算一次,那我们为何不去利用j-1的结果呢?也就是说我们将j-1的结果保存下来,在计算j步的结果时候,只需要在j-1步的基础上再加上a[j],就可以啦,于是有啦算法二。
算法二:
#include
using namespace std;
int Find_Maxsun2(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int Find_Maxsun2(int*a, int n){
int i, j, NewSum = 0, MaxSum= 0;
for (i = 0; i NewSum = 0;
for (j = i; j NewSum += a[j]; /*每一次在j-1条件下更新NewSum*/
if (NewSum>MaxSum) /*更新MaxSum*/
MaxSum = NewSum;
}
}
return MaxSum;
}
这个算法比1聪明,算法复杂度是O(n2),显然还不是我们想要的复杂度。
算法三:
算法三使用的是分治法的思想,基本思想不言而喻先分后治,将问题分解为小问题然后在可以总和小问题来解决,我们把原序列一分为二,那么最大子序列在左边,在右边,或者跨越边界,基本思路如下:
第一步:将原序列一分为二,分成左序列和右序列。
第二步:递归求出子序列S左和S右。
第三部:从中分线向两边扫描,找出跨越中线的最大子序列和S中。
第四步:求得S=max{S左,S中,S右};
代码实现如下:
#include
using namespace std;
int Find_MaxSum3(int*a,int low,int high);
int Max(int a,int b,int c);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int Find_MaxSum3(int*a,int low,int high){
int MaxSum = 0, MidSum, LeftSum, RightSum,i;
MidSum = 0;
if (low == high){ /*递归的终止条件*/
if (a[low] > 0)
return a[low];
else
return 0;
}
int mid = (low + high) / 2; //找到分的中点
LeftSum = Find_MaxSum3(a, low, mid); /*递归找到左边序列最大和*/
RightSum = Find_MaxSum3(a, mid + 1, high); /*递归找到右边序列最大子序列和*/
/*然后可以求中间跨越边界序列的最大和*/
int NewLeft = 0,Max_BorderLeft=0, NewRight = 0,Max_BorderRight=0;
for (i = mid; i >= low; i--){ /*向左扫描找到最大和*/
NewLeft += a[i];
if (NewLeft > Max_BorderLeft)
Max_BorderLeft = NewLeft;
}
for (i = mid + 1; i NewRight+=a[i];
if (NewRight >= Max_BorderRight)
Max_BorderRight = NewRight;
}
MidSum = Max_BorderRight + Max_BorderLeft;
return Max(LeftSum, MidSum, RightSum); /*返回治的结果*/
}
int Max(int a, int b, int c){ /*找出3者中最大的数*/
if ( a>= b&&a >= c)
return a;
if (b >= a&&b >= c)
return b;
if (c >= b&&c>=a)
return c;
}
我们来算一算这个算法时间复杂度:
T(1)=1;
T(n)=2T(n/2)+O(n);
=2kT(n/2k)+kO(n)=2kT(1)+kO(n)(其中n=2k)=n+nlogn=O(nlogn);
虽然这个算法已经非常好啦,但是并不是最快的算法。
算法四:
算法四叫做在线处理。意思为,每读入一个数据就进行及时处理,得到的结果是对于当前读入的数据都成立,即为在任何位置终止读入,算法都可以给出正确的解,边读边解。
#include
using namespace std;
int Find_MaxSum4(int*a, int n);
int main(){
int n, i;
int a[100];
cin >> n;
cout for (i = 0; i cin >> a[i];
cout return 0;
}
int Find_MaxSum4(int*a, int n){
int i, NewSum = 0, MaxSum = 0;
for (i = 0; i NewSum += a[i]; /*当前子序列和*/
if (MaxSum MaxSum = NewSum; /*更新最大子序列和*/
if (NewSum NewSum = 0;
}
return MaxSum;
}
这种算法是将读入的数据一个个扫描一遍,只有一个for循环,解决同一个问题算法差别大,在于一个窍门,让计算机记住一些关键的中间结果,避免重复计算。

PHP and Python each have their own advantages, and the choice should be based on project requirements. 1.PHP is suitable for web development, with simple syntax and high execution efficiency. 2. Python is suitable for data science and machine learning, with concise syntax and rich libraries.

PHP is not dying, but constantly adapting and evolving. 1) PHP has undergone multiple version iterations since 1994 to adapt to new technology trends. 2) It is currently widely used in e-commerce, content management systems and other fields. 3) PHP8 introduces JIT compiler and other functions to improve performance and modernization. 4) Use OPcache and follow PSR-12 standards to optimize performance and code quality.

The future of PHP will be achieved by adapting to new technology trends and introducing innovative features: 1) Adapting to cloud computing, containerization and microservice architectures, supporting Docker and Kubernetes; 2) introducing JIT compilers and enumeration types to improve performance and data processing efficiency; 3) Continuously optimize performance and promote best practices.

In PHP, trait is suitable for situations where method reuse is required but not suitable for inheritance. 1) Trait allows multiplexing methods in classes to avoid multiple inheritance complexity. 2) When using trait, you need to pay attention to method conflicts, which can be resolved through the alternative and as keywords. 3) Overuse of trait should be avoided and its single responsibility should be maintained to optimize performance and improve code maintainability.

Dependency Injection Container (DIC) is a tool that manages and provides object dependencies for use in PHP projects. The main benefits of DIC include: 1. Decoupling, making components independent, and the code is easy to maintain and test; 2. Flexibility, easy to replace or modify dependencies; 3. Testability, convenient for injecting mock objects for unit testing.

SplFixedArray is a fixed-size array in PHP, suitable for scenarios where high performance and low memory usage are required. 1) It needs to specify the size when creating to avoid the overhead caused by dynamic adjustment. 2) Based on C language array, directly operates memory and fast access speed. 3) Suitable for large-scale data processing and memory-sensitive environments, but it needs to be used with caution because its size is fixed.

PHP handles file uploads through the $\_FILES variable. The methods to ensure security include: 1. Check upload errors, 2. Verify file type and size, 3. Prevent file overwriting, 4. Move files to a permanent storage location.

In JavaScript, you can use NullCoalescingOperator(??) and NullCoalescingAssignmentOperator(??=). 1.??Returns the first non-null or non-undefined operand. 2.??= Assign the variable to the value of the right operand, but only if the variable is null or undefined. These operators simplify code logic, improve readability and performance.


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

MantisBT
Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

ZendStudio 13.5.1 Mac
Powerful PHP integrated development environment

SublimeText3 Chinese version
Chinese version, very easy to use

PhpStorm Mac version
The latest (2018.2.1) professional PHP integrated development tool

SecLists
SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.