Fork me on GitHub

最大子列和问题

发表于 | 分类于
7-1最大子列和问题

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

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

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

输入格式:

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

输出格式:

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

输入样例:

1
2
6
-2 11 -4 13 -5 -2

输出样例:

1
20

codes

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
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        String string=scanner.nextLine();
        String[] str_arr = string.split(" ");
        int array[] = new int[str_arr.length];

        for (int i = 0; i < str_arr.length; i++) {
            array[i] = Integer.parseInt(str_arr[i]);
        }
        int max_sum =process_online(array, array.length);
        System.out.println(max_sum);
    }
    //O(n^2)
    public static int getMaxSubSequenceSum(int array[], int n) {
        int this_sum,max_sum;
        this_sum=0;
        max_sum=0;
        for (int i = 0; i < n; i++) {
            this_sum=0;
            for (int j = i; j < n; j++) {
                this_sum += array[j];
                if (this_sum > max_sum) {
                    max_sum = this_sum;
                }
            }
        }
        return max_sum;
    }

    //O(nlog(n))

    public static int max_three(int a, int b, int c) {
        int temp=a>b?a:b;
        return temp > c ? temp : c;
    }
    public static int getCrossMax(int array[], int low, int mid, int hign) {
        int left_sum = 0;
        int right_sum = 0;
        int left_max = 0;
        int right_max = 0;
        for (int i = mid; i >= low; i--) {
            left_sum += array[i];
            if (left_sum > left_max) {
                left_max = left_sum;
            }
        }
        for (int i = mid + 1; i <= hign; i++) {
            right_sum += array[i];
            if (right_sum > right_max) {
                right_max = right_sum;
            }
        }
        return left_max + right_max;
    }

    public static int getMaxSubArraySum(int array[], int low, int hign) {
        if (low == hign) {
            return array[low];
        }

        int mid=low+(hign-low)/2;
        int left_sum = getMaxSubArraySum(array, low, mid);
        int right_sum = getMaxSubArraySum(array, mid + 1, hign);
        int cross_sum = getCrossMax(array, low, mid, hign);
        return max_three(left_sum, right_sum, cross_sum);
    }


    //O(n)
    public static int process_online(int array[], int n) {
        int this_sum,max_sum;
        this_sum=max_sum=0;

        for (int i = 0; i < n; i++) {
            this_sum += array[i];
            if (this_sum > max_sum) {
                max_sum = this_sum;
            }
            if (this_sum <= 0) {
                this_sum = 0;
            }
        }
        return max_sum;
    }
}