陈越姥姥的数据结构-01-二分查找-最大子列和问题

发表于 更新于 分类于

2022 年 3 月 1 日开课啦！
报名链接：https://www.icourse163.org/learn/ZJU-93001?tid=1466830443

常用软件下载
https://bytodance.feishu.cn/docs/doccn7ZRXBvN8HMEfF8LNq9gKig
备用下载地址
https://pan.mhatp.cn/%E8%BD%AF%E4%BB%B6

01-复杂度3 二分查找 (20 分)

复习一下二分查找模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Position BinarySearch( List L, ElementType X )
{
    int l=1,r=L->Last;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(L->Data[mid] >= X){
            r = mid;
        }else{
            l = mid + 1;
        }
    }
    if(L->Data[r] == X){
        return r;
    }else{
        return NotFound;
    }
    
}

01-复杂度1 最大子列和问题 (20 分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
// typedef long long ll;
// 后来发现 int 也能过
using namespace std;

const int N = 1e5 + 10;

int n;
int arr[N];
int thissum = 0, maxsum = -0x3f3f3f;

int main() {
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    for (int i = 0; i < n; i++) {
        thissum += arr[i];
        if (thissum < 0) thissum = 0;
        maxsum = max(maxsum, thissum);
    }

    printf("%d", maxsum);
    return 0;
}

01-复杂度2 Maximum Subsequence Sum (25 分)

不知道哪错了，呜呜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
typedef long long ll;
using namespace std;

const int N = 1e5 + 10;

int n;
int arr[N];
int thissum = 0, maxsum = -0x3f3f3f;

int main() {
    
    scanf("%d", &n);

    for (int i = 0; i < n; i++)  scanf("%d", &arr[i]);

    int maxl, maxr;
    
    bool first = true;
    
    int thisl,thisr;

    for (int i = 0; i < n; i++) {
        
        thissum += arr[i];
       
        if(first){
            thisl = i;
            thisr = i;
            first = false;
        }else{
            thisr = i;
        }
        
         
        if (thissum < 0) {
           // 重新开始一个
            
            thissum = 0;

            first = true;
        }
        
        
        if (thissum > maxsum) {
            maxsum = thissum;
            maxl = thisl;
            maxr = thisr;
        }
        
        
    }
    
    printf("%d %d %d\n", maxsum, maxl, maxr);
    
    return 0;
}

测试视频，请忽视