Fork me on GitHub

最大子列和

发表于 | 分类于

img

O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//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)

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
//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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//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;
}