专栏首页猿计划分治策略之最大子数组(Python实现)

分治策略之最大子数组(Python实现)

一、 实验目的及任务

分治法求解最大子数组问题

二、 实验环境

c++或java

三、 问题描述

Input : 一个数组

Output:最大连续子数组。

四、 编程任务

一个整数数组中的元素有正有负,在该数组中找出一个连续子数组,要求该连续子数组中各元素的和最大,这个连续子数组便被称作最大连续子数组。

五、 数据输入

随机产生1000以上的数据(有正有负),放入输入文件input.txt

六、 结果输出

比如数组{2,4,-7,5,2,-1,2,-4,3}的最大连续子数组为{5,2,-1,2},最大连续子数组的和为5+2-1+2=8。

七、 实验报告内容

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

实验结果

结果1:使用课本上的测试数据:[12,5,1,9,-11]进行排序

结果2:随机生成1100000个数字,从-5000到182000,存入到input1.txt文件中

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 剑指 Offer 28. 对称的二叉树

    请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

    TrueDei
  • LeetCode 剑指Offer 面试题27. 二叉树的镜像

    输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1]

    TrueDei
  • 牛客网-二叉树的镜像

    操作给定的二叉树,将其变换为源二叉树的镜像。 输入描述: 二叉树的镜像定义:源二叉树 8 / 6 10 / \ / 5 7 9 11...

    TrueDei
  • 【LeetCode】(No.011) 盛最多水的容器

    给定 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai...

    PM小王
  • 算法:动态规划(DP)入门实践

    keloli
  • 大数据技术之_19_Spark学习_03_Spark SQL 应用解析小结

    ========== Spark SQL ========== 1、Spark SQL 是 Spark 的一个模块,可以和 RDD 进行混合编程、支持标准的数据...

    黑泽君
  • go 自定义排序

    超级大猪
  • RabbitMQ扩展之消费者优先级

    正常情况下,所有订阅同一个队列的活跃消费者以循环的(round-robin)方式从队列中接收消息。当使用了消费者优先级,如果多个活跃消费者使用了相同的高优先级属...

    Throwable
  • 喜报!腾讯云主机安全入选Gartner CWPP全球市场指南

    随着万物网联和企业上云成为了主流趋势,对于正在数字化转型的企业而言,主机作为承载数据资产和业务管理的基础设施,其安全防护重要性日益凸显;与此同时,虚拟机、云主机...

    腾讯安全
  • AI百度接口以及图灵接口的使用

    耳朵 = 倾听 = 麦克风 = 语音识别 ASR:Automatic Speech Recognition

    GhostCN_Z

扫码关注云+社区

领取腾讯云代金券