01-复杂度1 最大子列和问题

给定KK个整数组成的序列 {N1, N2,..., Nk}，“连续子列”被定义 {Ni, N(i+1),..., Nj}，其中 1 ≤ 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

代码实现

Python

O(n^2)

def MaxSubSequenceSum(lst, n):
    MaxSum = 0
    i = 1
    while i < n:
        ThisSum = 0
        j = i
        while j < n:
            ThisSum += lst[j]
            if ThisSum > MaxSum:
                MaxSum = ThisSum
            j += 1
        i += 1
    print(MaxSum)

def main():
    n = int(input())
    lst = input()
    lst = [int(e) for e in lst.split()]
    MaxSubSequenceSum(lst, n)

main()

O(nlogn)

def DivideAndConquer(lst, left, right):
    if left == right:
        if lst[left] > 0:
            return lst[left]
        else:
            return 0

    center = (left + right) // 2
    MaxLeftSum = DivideAndConquer(lst, left, center)
    MaxRightSum = DivideAndConquer(lst, center + 1, right)

    MaxLeftBorderSum = LeftBorderSum = 0
    i = center
    while i >= left:
        LeftBorderSum += lst[i]
        if LeftBorderSum > MaxLeftBorderSum:
            MaxLeftBorderSum = LeftBorderSum
        i -= 1

    MaxRightBorderSum = RightBorderSum = 0
    i = center + 1
    while i <= right:
        RightBorderSum += lst[i]
        if RightBorderSum > MaxRightBorderSum:
            MaxRightBorderSum = RightBorderSum
        i += 1

    return max([MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum])

def main():
    n = int(input())
    lst = input()
    lst = [int(e) for e in lst.split()]
    print(DivideAndConquer(lst, 0, n - 1))
main()

O(n)

def OnlineProcessing(list):
    # list = map(int, list.split()) # map 可遍历，但是不能根据位置取数据。
    list = [int(e) for e in list.split()]
    ThisSum = MaxSum = 0
    for e in list:
        ThisSum += e
        if ThisSum > MaxSum:
            MaxSum = ThisSum
        elif ThisSum < 0:
            ThisSum = 0
    print(MaxSum)
def main():
    n = int(input())
    if n > 0:
        list = input()
        OnlineProcessing(list)
main()

C语言

O(n)

#include<stdio.h>

int main() 
{
    const int N = 100000;
    int n;
    int A[N];
    int ThisSum = 0, MaxSum = 0;

    scanf("%d", &n);

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

    for ( int i = 0; i < n; i++ ) {
        ThisSum += A[i];
        if ( ThisSum > MaxSum ) {
            MaxSum = ThisSum;
        } else if ( ThisSum < 0 ) {
            ThisSum = 0;
        }
    }
    printf("%d", MaxSum);

    return 0;
}

#将计算最大子列和打包为一个函数。
#include<stdio.h>

void OnlineProcessing(int A[], int n);
int main() 
{
    const int N = 100000;
    int n;
    int A[N];

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }   
    // 注意调用方法（调用用A而不是A[]）
    OnlineProcessing(A, n);

    return 0;
}

void OnlineProcessing(int A[], int n) {
    int ThisSum = 0, MaxSum = 0;
    for ( int i = 0; i < n; i++ ) {
        ThisSum += A[i];
        if ( ThisSum > MaxSum ) {
            MaxSum = ThisSum;
        } else if ( ThisSum < 0 ) {
            ThisSum = 0;
        }
    }
    printf("%d", MaxSum);
}