1.算法的概念
- 一个有限指令集
- 接受一些输入（有时不需要输入）
- 产生输出
- 在有限步骤之后终止
- 每一条指令必须:
<1>.有充分目标，不可以有歧义
<2>.计算机能处理的范围内
<3>.描述不依赖任何一种计算机语言以及具体实现手段
2.评判好算法指标
- 空间复杂度S(n):程序执行时占用存储单元的长度
- 时间复杂度T(n):程序执行时耗费时间的长度
3.分析算法好坏所关注的复杂度
- 最坏情况复杂度（一般分析这个）
- 平均复杂度
4.复杂度排序
tips：
- logn不写底是因为无关紧要，都一样
- 作为程序员，遇到n的二次方试着将其降为nlogn
5.复合算法复杂度
-
若两段算法的复杂度分别为：T1(n)=O(f1(n)),T2(n)=O(f2(n))则：
<1>.T1(n)+T2(n)=max(O(f1(n)),O(f2(n)))
<2>.T1(n)*T2(n)=O(f1(n)*f2(n)) -
for：循环次数*循环体代码的复杂度
-
if-else：取决于if条件复杂度和两个分支部分复杂度，总体复杂度取三者中最大
6.应用实例-最大子链和
给定N个整数的序列，求最大子链和，若结果为负，返回0；
-
方法1：复杂度-N的三次方
暴力的三次循环求解 -
方法2：复杂度-N的二次方
改进ThisSum求和的一步，每次求和都是在原有的基础之上继续加了一个数，让原本第三个for下的运算跟着第二个走 -
方法3：复杂度-nlogn-分而治之
<1>.[4,-3,5,-2,-1,2,6,-2]首先将其分为左[4,-3,5,-2],右[-1,2,6,-2]两个部分
<2>.继续分：[4,-3],[5,-2],[-1,2],[6,-2]<3>.[4,-3],以4和-3的中间向左右两边扫描，左最大4，从中向左最大4，右边最大-3，从中向右最大-3，子链{4,-3}最大 = （从中向左最大+从中向右最大）=1，[4,-3]最大 = max（左最大，右最大，子链{4,-3}最大 ）=4
<4>.同理 [5,-2]最大 = 5<5>.[4,-3,5,-2],以[4,-3]和[5,-2]的中间向左右两边扫描，左最大4，从中向左最大1，右边最大5，从中向右最大3，子链{4,-3,5,-2}最大 = （从中向左最大+从中向右最大）=4，[4,-3]最大 = max（左最大，右最大，子链{4,-3,5,-2}最大 ）=5
<5>.同理[-1,2,6,-2]最大 = 8<6>.[4,-3,5,-2,-1,2,6,-2],以[4,-3,5,-2]和[-1,2,6,-2]的中间向左右两边扫描，左最大5，从中向左最大4，右边最大8，从中向右最大7，子链{4,-3,5,-2,-1,2,6,-2}最大 = （从中向左最大+从中向右最大）=11，[4,-3,5,-2,-1,2,6,-2]最大 = max（左最大，右最大，子链{4,-3,5,-2,-1,2,6,-2}最大 ）=11
-
方法4：复杂度-N-在线处理
[-3，1，-2，2，-1，2，-3]从左向右依次扫描，-3抛弃，max = 0,整个结果加上负数结果一定会比原来小;1，保留，max = 1;1-2=-1,负数抛掉，max = 1；2保留，max = 2；2-1 = 1保留，max = 2；1+2 = 3保留，max = 3；3-3 = 0保留，max = 3；故max = 3
#include<iostream>
using namespace std;
int N = 8;
int A[8] = {4,-3,5,-2,-1,2,6,-2};
int MaxSubseqSum1(int A[],int N); //way1
int MaxSubseqSum2(int A[],int N); //way2
int MaxSubseqSum3(int A[],int left,int right); //way3
int MaxSubseqSum4(int A[],int N); //way4
int max3(int a,int b, int c); //获取a,b,c中最大值
int main(){
int result;
//result = MaxSubseqSum1(A,N);
//result = MaxSubseqSum2(A,N);
result = MaxSubseqSum3(A,0,N-1);
//result = MaxSubseqSum4(A,N);
cout<<result<<endl;
return 0;
}
int MaxSubseqSum1(int A[],int N){
int MaxSum = 0;
for(int i=0;i<N;i++){
for(int j=i;j<N;j++){
cout<<"MaxSum:"<<MaxSum<<endl;
int ThisSum = 0;
for(int k=i;k<j;k++){
ThisSum += A[k];
}
if(ThisSum>MaxSum){
MaxSum = ThisSum;
}
}
}
return MaxSum;
}
int MaxSubseqSum2(int A[],int N){
int MaxSum = 0;
for(int i=0;i<N;i++){
int ThisSum = 0;
for(int j=i;j<N;j++){
ThisSum += A[j];
cout<<"MaxSum:"<<MaxSum<<endl;
if(ThisSum>MaxSum){
MaxSum = ThisSum;
}
}
}
return MaxSum;
}
int MaxSubseqSum3(int A[],int left,int right){
if(left == right){
//分到底的情况
if(A[left] > 0){
return A[left];
}
else{
return 0;
}
}
int center = (left+right)/2; //1/2为0，向0取整
int maxLeft = MaxSubseqSum3(A,left,center); //递归获取左右两端的最大值
int maxRight = MaxSubseqSum3(A,center+1,right);
int leftBorderSum = 0;
int leftBorderMax = 0;
for(int i=center;i>=left;i--){
//左边最大值
leftBorderSum += A[i];
if(leftBorderSum > leftBorderMax){
leftBorderMax = leftBorderSum;
}
}
int rightBorderSum = 0;
int rightBorderMax = 0;
for(int i=center+1;i<=right;i++){
//右边最大值
rightBorderSum += A[i];
if(rightBorderSum > rightBorderMax){
rightBorderMax = rightBorderSum;
}
}
return max3(maxLeft, maxRight, leftBorderMax + rightBorderMax);
}
int MaxSubseqSum4(int A[],int N){
int MaxSum,ThisSum = 0;
MaxSum = ThisSum = 0;
for(int i=0;i<N;i++){
ThisSum += A[i];
if(ThisSum>MaxSum){
MaxSum = ThisSum;
}
else if(ThisSum < 0){
ThisSum = 0;
}
cout<<"MaxSum:"<<MaxSum<<endl;
}
return MaxSum;
}
int max3(int a,int b, int c){
int max = a>b?a:b;
max = max>c?max:c;
return max;
}