算法设计与分析课程中最大子段和问题的教学探讨

Discussion of Maximum Sub-Segment Sum Problem in Course of Design and Analysis of Algorithm

介绍算法设计与分析课程中最大子段和问题的动态规划解法,其求解思想是先求给定序列中以每一个元素为尾元素的最大子段和,然后其中的最大者便是整个序列的最大子段和。从两个不同的角度分析最大子段和问题最优解的构造方法,给出最大子段和问题的动态规划算法,并分析算法的时间复杂度。通过这一问题的讲解,有助于学生明确动态规划方法的解题步骤,掌握动态规划算法的设计步骤。

The paper introduces a dynamic programming method of maxinmm sub-segment sum problem in the course of design and analysis of algorithm. The solution procedure is to solve the maximum sub-segment sum of each element used as the tail element in a given sequence firstly, and then one of the largest is the maximum sub-segment sum of the whole sequence. The paper analyzes the construction method of the optimal solution of the maximum sub-segment sum problem from two different facet, and presents the dynamic programruing algorithm of the maximum sub segment sum problem, also analyzes the time complexity of the algorithm. Through the explanation of this problem, it will help the students clear the solving steps of the dynamic programming method and master the design step of the dynamic programl＇ning algorithm.