发表于

test！

发表于   |   分类于

给定KK个整数组成的序列{ N_1N
​1
​​ , N_2N
​2
​​ , …, N_KN
​K
​​ }，“连续子列”被定义为{ NiN
​i
​​ , N{i+1}N
​i+1
​​ , …, N_jN
​j
​​ }，其中 1 \le i \le j \le K1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

数据1：与样例等价，测试基本正确性；
数据2：102个随机整数；
数据3：103个随机整数；
数据4：104个随机整数；
数据5：105个随机整数；
输入格式:

输入第1行给出正整数KK (\le 100000≤100000)；第2行给出KK个整数，其间以空格分隔。

输出格式:

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

输入样例:
6
-2 11 -4 13 -5 -2
输出样例:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
时间复杂度：O(n)
#include<stdio.h>
#define MAXN 100000
int arr[MAXN+10];
int main(void)
{
    int n, i, thisSum, maxSum, begin, end, index;
    
    scanf("%d", &n);
    for(i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    
    thisSum = maxSum = index = 0;
    for(i = 0; i < n; i++)
    {
        thisSum += arr[i];
        if(thisSum > maxSum)
        {
            maxSum = thisSum;
            begin = index;
            end = i;
        }
        if(thisSum < 0)
        {
            thisSum = 0;
            index = i+1;
        }
    }
    
    if(maxSum == 0)
    {
        for(i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                break;
        }
        if(i == n) // 所有元素都是负数
            printf("%d %d %d\n", 0, arr[0], arr[n-1]);
        else
            printf("0 0 0\n");
    }
    else
        printf("%d %d %d\n", maxSum, arr[begin], arr[end]);
    return 0;
}
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
时间复杂度O(nlog(n))
#include<stdio.h>
#define MAXN 100000
int MaxSeqSum(int arr[], int low, int high);
int MaxOfThree(int a, int b, int c);
int arr[MAXN+10];
int G_MAX = 0;  
int G_LeftIndex = 0;
int G_RightIndex = 0;
int main(void)
{
    int i, n, ans;
    
    scanf("%d", &n);
    for(i = 0; i < n; i++)
        scanf("%d", &arr[i]);
         
    ans = MaxSeqSum(arr, 0, n-1);
    printf("%d", ans);
    if(ans == 0)
    {
        for(i = 0; i < n; i++)
            if(arr[i] == 0)
                break;
        
        if(i == n)
            printf(" %d %d", arr[0], arr[n-1]);
        else 
            printf(" %d %d", 0, 0);
    }
    else
        printf(" %d %d", arr[G_LeftIndex], arr[G_RightIndex]);
    return 0;
}
int MaxSeqSum(int arr[], int low, int high) // 左闭右闭区间
{
    int i, leftBoundIndex, rightBoundIndex, mid;
    int max1, max2, max3, thisSum, maxLeftSum, maxRightSum, localMax;
    
    if(low == high)
    {
        if(arr[low] <= 0)
            return 0;
        else 
            return arr[low];
    }
        
    mid = low + ((high-low) >> 1); // 注意优先级,这里栽了好几次了Orz...
    max1 = MaxSeqSum(arr, low, mid);
    max2 = MaxSeqSum(arr, mid+1, high);
    
    thisSum = maxLeftSum = 0;
    for(i = mid; i >= low; i--)
    {
        thisSum += arr[i];
        if(thisSum > maxLeftSum)
        {
            maxLeftSum = thisSum;
            leftBoundIndex = i;
        }
    }
    thisSum = maxRightSum = 0;
    for(i = mid+1; i <= high; i++)
    {
        thisSum += arr[i];
        if(thisSum > maxRightSum)
        {
            maxRightSum = thisSum;
            rightBoundIndex = i;
        }
    }
    
    max3 = maxLeftSum + maxRightSum;
    localMax = MaxOfThree(max1, max2, max3);
    if(G_MAX < localMax)
    {
        G_MAX = localMax;
        
        if(max1 == G_MAX)
        {
            G_LeftIndex = G_RightIndex = low;
        }
        else if(max3 == G_MAX)
        {
            if(max3 == max2) // 左边界未初始化,为垃圾值,至于右边界的问题在第一个if里已经得到了处理
                G_LeftIndex = rightBoundIndex;
            else
                G_LeftIndex = leftBoundIndex;
            G_RightIndex = rightBoundIndex;
        }
        else 
        {
            G_LeftIndex = G_RightIndex = high;
        }
    }    
//    printf("%d %d\n", low, high); // test
//    printf("%d %d\n", G_LeftIndex, G_RightIndex); 
    return localMax;
}
int MaxOfThree(int a, int b, int c)
{
    int max = a;
    if(b > max)
        max = b;
    if(c > max)
        max = c;
    return max;
}

发表于

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment