分治策略之最大子数组（Python实现）

import random
import math

#随机生成数
def randomData():
    # 打开input文件
    file = open('input.txt', 'w', encoding='utf8');

    print("正在随机生成数据，写入input.txt文件")
    # 产生10万个数据，从0到100000
    i = 0;
    while i < 110000:
        file.write(str(random.randint(-5000, 110000))+"\n")
        i = i + 1;
    file.close()
    print("写入input.txt文件完毕")


#一、输入n个整数，求出连续的m个的和最大。


#打开input.txt文件   读取文件
def readLine():
    # 行数
    count_line = 0;
    # 定义存储的元组
    arr1 = []
    file = open('input.txt', 'r', encoding='utf8');
    for line in file.read().splitlines():
        arr1.append(int(line))
        count_line = 1 + count_line;  # 计算行数
    file.close();
    return arr1;


def writeLine(A,arrA):
    # 打开input文件
    file = open('output.txt', 'w', encoding='utf8');
    print("正在打开output.txt文件")
    i = arrA[0];
    while i < arrA[1]:
        file.write(str(A[i]) + "\n")
        i = i + 1;
    file.close()
    print("结果写入output.txt文件完毕")


def FIND_MAXIMUM_SUBARRAY(A,low,high):
    if high == low:
        return [low,high,A[low-1]]
    else:
        mid = math.floor((low+high)/2) #向下取整
        left = FIND_MAXIMUM_SUBARRAY(A,low,mid)
        right = FIND_MAXIMUM_SUBARRAY(A, mid+1, high)
        cross = FIND_MAX_CROSSING_SUBARRAY(A, low, mid,high)
        if left[2] >= right[2] and left[2] >= cross[2]:
            return left
        elif right[2] >= left[2] and  right[2] >=  cross[2]:
            return right
        else:
            return cross

def FIND_MAX_CROSSING_SUBARRAY(A,low, mid,high):
    left_sum =  -1568413122
    sum = 0
    max_left = 0
    for i in range(mid, low,-1):
        sum = sum + int(A[i])
        if sum > left_sum:
            left_sum = sum
            max_left = i

    right_sum = -1568413122
    sum = 0
    max_right = 0
    for j in range(mid+1,high):
        sum = sum + A[j]
        if sum > right_sum:
            right_sum = sum
            max_right = j
    return [max_left,max_right,(left_sum+right_sum)]  #结果 [0, 109999, 2888566239]



if __name__ == '__main__':
    #随机生成数据并存放在input.txt文件中
    randomData();
    #读取数据
    print("正在获取数据")
    A = readLine();
    # A = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]
    low = 0;
    high = len(A)
    arrA = FIND_MAXIMUM_SUBARRAY(A,low,high)
    print("结果",arrA)
    writeLine(A,arrA)


# for i in "100000":
#     print(i)
#     print(random.randint(1,100))