算法设计与分析第二章作业

题目：

AC代码：

#include<bits/stdc++.h>
using namespace std;
int a[100010],s[100010];
//分治
int solve(int l,int r){
if(l==r){
if(a[l]<0)return 0;
return a[l];
}
int mid=(l+r)/2;
int sl=solve(l,mid),sr=solve(mid+1,r);
//向左
int s1=0,t=0;
for(int i=mid;i>=l;i--){
t+=a[i];
s1=max(t,s1);
}
//向右
int s2=0;t=0;
for(int i=mid+1;i<=r;i++){
t+=a[i];
s2=max(t,s2);
}
int sm=s1+s2;
return max(sm,max(sl,sr));
}
int main(){
int n;
cin>>n;
bool f=1;
for(int i=1;i<=n;i++){
cin>>a[i];
// if(a[i]>=0){
// f=0;
// }
}
cout<<solve(1,n);
// int ma=-1,now=0;
// for(int i=1;i<=n;i++){
// if(now+a[i]>0){
// now+=a[i];
// ma=max(ma,now);
// }else{
// now=0;
// }
// }
// if(f){
// cout<<0;
// }else{
// cout<<ma;
// }
return 0;
}作业：

1. 请以伪代码描述最大子段和的分治算法
//数组的最大子段和有三种可能：
//1.与左半部分的最大子段和相同，为sl
//2.与右半部分的最大子段和相同，为sr
//3.最大子段和跨越了两部分，为sm=s1+s2，s1和s2分别为从中间开始向左右两边计算最大子段和
int solve(int l,int r){
//递归终止条件
if(l==r){
//最小子问题，l==r，此时若该数>0则返回改数，否则返回0
}
//将数组从中间(mid=(l+r)/2)切开，分为a[1:mid]和a[mid+1:n]，递归调用solve得到sl和sr，分别代表左边和右边的最大子段和
for(int i=mid;i>=l;i--){
//从中间向左累计s1，得最大值
}
for(int i=mid+1;i<=r;i++){
//从中间向右累计s2，得最大值
}
return //三种情况的最大值
}

2. 分析该算法的时间复杂度
由公式及以下分析：

1.划分：时间复杂度为O(1)；

2.求解子问题：每次将问题规模为n的数组划分成2个规模为n/2的子问题，分别对这两个子数组进行递归操作，时间复杂度为2T(n/2)；

3.合并：对两个子数组进行合并，时间复杂度为O(n)；

得：

T(n) = O(1) n<=1;

​ 2T(n/2) + O(n) n>1;

得该算法的时间复杂度为O(nlogn)。

3. 结合本章的学习，你对分治法的体会和思考
分治法就是 **将大问题分解成小问题，再从小问题入手，分而治之，最后再合并子问题的解 **的一种基本的算法思想0

分治法的三个基本步骤：

1、分解子问题

2、求解子问题（递归调用）

3、合并子问题的解