首页 杭电 Oj

# 题目信息

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 377960 Accepted Submission(s): 90742

# Problem Description

Given a sequence a[1],a[2],a[3]…a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.

# Input

The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).

# Output

For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.

# Sample Input

1
2
3
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

# Sample Output

1
2
3
4
5
Case 1:
14 1 4

Case 2:
7 1 6

# 题解

# C 语言解法

# 动态规划

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
#include <stdio.h>

/**
 * 动态规划。
 * @return
 */
int main() {
    int caseCount;
    int caseIndex = 0;
    scanf("%d", &caseCount);
    while ((caseIndex) < caseCount) {
        int num[100001] = {0};
        int sum[100001] = {0};
        int n = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
        }

        int maxSum = sum[0] = num[0];
        int startIndex = 0;
        int endIndex = 0;
        int temp = 0;
        for (int i = 1; i < n; ++i) {
            if (sum[i - 1] < 0) {
                sum[i] = num[i];
                temp = i;
            } else {
                sum[i] = num[i] + sum[i - 1];
            }

            if (maxSum < sum[i]) {
                maxSum = sum[i];
                endIndex = i;
                startIndex = temp;
            }
        }

        printf("Case %d:\n", ++caseIndex);
        printf("%d %d %d\n", maxSum, startIndex + 1, endIndex + 1);

        if (caseIndex < caseCount) {
            printf("\n");
        }
    }
    return 0;
}

反过头来，继续看这段代码的话，我们可以发现，其实我们只用了 sum[i-1] 这一个值， sum[i-2]....sum[0] 我们是没有什么用的。所以我们可以使用一个变量才替换 sum 数组。

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
#include <stdio.h>

/**
 * 动态规划。
 * @return
 */
int main() {
    int caseCount;
    int caseIndex = 0;
    scanf("%d", &caseCount);
    while ((caseIndex) < caseCount) {
        int n = 0;
        int a, previous = 0;
        int max = 0;
        int startIndex, endIndex;
        int temp = startIndex = endIndex = 1;
        scanf("%d %d", &n, &previous);
        max = previous;
        for (int i = 2; i <= n; ++i) {
            scanf("%d", &a);
            if (previous < 0) {
                previous = a;
                temp = i;
            } else {
                previous += a;
            }

            if (previous > max) {
                max = previous;
                endIndex = i;
                startIndex = temp;
            }
        }

        printf("Case %d:\n", ++caseIndex);
        printf("%d %d %d\n", max, startIndex , endIndex);

        if (caseIndex < caseCount) {
            printf("\n");
        }
    }
    return 0;
}

# 滑动窗口法

注意： 这种解法是会 Time Limit Exceeded 的。

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
/**
 * 滑动窗口法。
 * @return
 */
int main() {
    int caseCount;
    int caseIndex = 0;
    scanf("%d", &caseCount);
    while ((caseIndex) < caseCount) {
        int num[100000] = {0};
        int n = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%d", &num[i]);
        }
        int maxStartIndex = 0;
        int width = n;
        int maxSum = -10000;
        int maxWidth = 0;
        while (width > 0) {
            for (int i = 0; i <= n - width; ++i) {
                int sum = 0;
                for (int j = 0; j < width; j++) {
                    sum += num[i + j];
                }
                if (maxSum < sum) {
                    maxSum = sum;
                    maxStartIndex = i;
                    maxWidth = width;
                }
            }
            width--;
        }

        printf("Case %d:\n", ++caseIndex);
        printf("%d %d %d\n", maxSum, maxStartIndex + 1, maxStartIndex + maxWidth);

        if (caseIndex < caseCount) {
            printf("\n");
        }
    }
    return 0;
}

# Be Careful

nothing…

# 链接

杭电Oj - 1003

http://acm.hdu.edu.cn/

【C】杭电Oj-1003题解-滑动窗口(C语言版)

https://gitee.com/fangjiaxiaobai/leetCode.git

【C】杭电Oj-1003题解-动态规划(C语言版)

https://gitee.com/fangjiaxiaobai/leetCode.git

【C】杭电Oj-1003题解-动态规划(优化版本)

https://gitee.com/fangjiaxiaobai/leetCode.git

# 最后

希望与你一起遇见更好的自己

期望与你一起遇见更好的自己

更新于 阅读次数 次

请我喝[咖啡]~(￣▽￣)~*

方小白 微信支付

微信支付

方小白 支付宝

支付宝

方小白 numberpay

numberpay