流离之人追逐幻影

用户名：pwj666

访问量：53905

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	35
经　　验	13258
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：142

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

01-复杂度--浙大数据结构-2019秋

　　作者: 流离之人追逐幻影　　　　发表时间：2019-10-24 20:42:41 浏览：245　|　评论：0　

```
01-复杂度1 最大子列和问题 (20 分)
```
![](/image_editor_upload/20191024082642_86653.png)
题解：
```
在线处理  时间复杂度O(n)
```
AC代码：
```
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int n,a,minsum=0,maxsum=0;
    cin>>n;
    while(n--){
        cin>>a;
        minsum+=a;
        if(minsum>maxsum)
            maxsum=minsum;
        if(minsum<0)
            minsum=0;
    }
    cout<<maxsum<<endl;

return 0;
}

```

------------

```
01-复杂度2 Maximum Subsequence Sum (25 分)
```
![](/image_editor_upload/20191024082904_71605.png)

题解+总结：
```
最大连续子序列（和+该最大连续序列的显示）
这题超级坑啊，做40+分钟，越做思路越乱，最后时刻冷静了5+分钟，思路才渐渐清晰，做这种看起来特殊处理很多的题目，首先第一步不看需要特殊处理，先把满足大部分情况的解弄出来，然后在对多种特殊情况继续做分类处理；总之做出满足大部分解的代码，然后再对特殊解的情况，对代码逐步修正。这样做起来才能更快！
```

AC代码：
```
#include<iostream>
using namespace std;
int main(){
	int n;
	int a[100000+5];
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	int left = 0;
	int tmpleft = 0;
	int right = n-1;
	int max =0;
	int tmpSum=0;
	int flag=0;
	for(int i=0;i<n;i++){
		tmpSum+=a[i];
		if(a[i]==0)flag=1;
		if(tmpSum<0){
			tmpSum=0;
			tmpleft = i+1;   // 开头的数就在这段被抛弃子序列的下一个
		}else if(max < tmpSum){
			max = tmpSum;
			left = tmpleft;   // 每次更新最大值也就确定了一段子序列，保存此时的开头
			right = i;       // 结尾的数就在每次更新最大值时
		}
	}
	if(max>0)
        cout<<max<<" "<<a[left]<<" "<<a[right];
	else
        if(flag)
            cout<<"0 0 0";
        else
            cout<<0<<" "<<a[0]<<" "<<a[n-1];
	return 0;
}
```

------------

```
01-复杂度3 二分查找 (20 分)
```
![](/image_editor_upload/20191024084027_41038.png)
![](/image_editor_upload/20191024084055_36202.png)
![](/image_editor_upload/20191024084121_79231.png)
题解：
```
二分查找算法  题型新颖，第一次做这类题
```
AC代码：
```
Position BinarySearch( List L, ElementType X ){
    ElementType r=L->Last;
    ElementType l=1;
    ElementType m=1;
    while(l<=r){
        m=(l+r)/2;
        if(X>L->Data[m])
            l=m+1;
        else
            if(X==L->Data[m])
             return m;
        else
            if(X<L->Data[m])
             r=m-1;
    }
    return NotFound;
}
```

0.0分

0 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言训练-8除不尽的数（C语言代码）

C语言训练-求素数问题（C语言代码）

C语言训练-立方和不等式（C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

01-复杂度--浙大数据结构-2019秋

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C++代码）

简单的a+b （C语言代码）

回文串（C语言代码）

打水问题（C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

【蟠桃记】（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言训练-8除不尽的数 （C语言代码）

C语言训练-求素数问题 （C语言代码）

C语言训练-立方和不等式 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

01-复杂度--浙大数据结构-2019秋

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C++代码）

简单的a+b （C语言代码）

回文串 （C语言代码）

打水问题 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

【蟠桃记】 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言训练-8除不尽的数（C语言代码）

C语言训练-求素数问题（C语言代码）

C语言训练-立方和不等式（C语言代码）

　　评论区

回文串（C语言代码）

打水问题（C语言代码）

【蟠桃记】（C语言代码）