蛮力法、分治法和动态规划法求解最大子数组问题的思考  

Thoughts on solving the maximum subarray problem by brute force method,divide and conquer method and dynamic programming method

作　　者：陈艳 文晓棠 Chen Yan;Wen Xiaotang(School of Data Science,Guangzhou Huashang College,Guangzhou 510520,China)

机构地区：[1]广州华商学院数据科学学院,广州510520

出　　处：《现代计算机》2023年第18期24-29,共6页Modern Computer

基　　金：2021年校级课程思政试点专业建设项目(HS2021KCSZ10)。

摘　　要：最大子数组问题是一个经典的算法问题,为了确定解决该问题的最有效方法,研究用于解决该问题的各种不同算法是十分必要的。通过分别应用蛮力法、分治法和动态规划法对该问题的求解思路和算法设计进行研究,并应用不同规模的数组对其进行对比测试,得到的试验结果表明,从算法的复杂度来看,动态规划算法是求解最大子数组问题的最有效方法。The maximum subarray problem is a classic algorithmic problem,and in order to determine the most effective method to solve it,it is necessary to study various algorithms used to solve the problem.By applying brute force method,divide and conquer method and dynamic programming method respectively to study the solution idea and algorithm design of this problem,and applying arrays of different scales to conduct comparative tests,the experimental results show that dynamic programming algorithm is the most effective method to solve the problem of the largest sub array from the complexity of the algorithm.

关 键 词：最大子数组问题 蛮力法 分治法 动态规划 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]