《算法设计与分析》课程设计报告题目：最大子段和问题院（系）：信息科学与工程学院专业班级：软件工程1201班2014年12月29日至2015年1月9日算法设计与分析课程设计任务书一、设计题目最大子段和问题问题描述：给定n个整数（可能有负整数）a1，a2，…，an。求形如ai，ai+1，…aji=1，2，…n，j=1，2，…n，i≤j，求出ai，ai+1，…aj子段和的最大值。当所有整数均为负值时定义其最大子段还和为0。例如：当(a1，a2，a3，a4，a5，a6)=(-2，11，-4，13，-5，2)时，最大子段和为(a2，a3，a4)=20即=20i=2，j=4二、设计主要内容具体要求如下：使用蛮力算法实现使用分治策略算法实现使用动态规划算法实现对各种算法的时间复杂度进行分析和比较。设计出相应的菜单，通过菜单的选择实现各个功能三、原始资料无四、要求的设计成果(1)实现该系统功能的程序代码(2)撰写符合规范要求的课程设计报告五、进程安排序号课程设计内容学时分配备注1选题与搜集资料1天2分析与设计1天3模块实现4天4系统调试与测试2天5撰写课程设计报告2天合计10天六、主要参考资料[1]吕国英．算法设计与分析．第2版．北京：清华大学出版社，2011．[2]王晓东．算法设计与分析．北京，清华大学出版社，2009．[3]徐士良．计算机常用算法．第2版．北京，清华大学出版社出版，2010．指导教师（签名）：20年月日目录TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc408472644"1常用算法PAGEREF_Toc408472644\h6HYPERLINK\l"_Toc408472645"1.1蛮力算法PAGEREF_Toc408472645\h6HYPERLINK\l"_Toc408472646"1.2分治算法PAGEREF_Toc408472646\h7HYPERLINK\l"_Toc408472647"1.3动态规划算法PAGEREF_Toc408472647\h8HYPERLINK\l"_Toc408472648"2问题分析与算法设计PAGEREF_Toc408472648\h9HYPERLINK\l"_Toc408472649"2.1蛮力算法的设计PAGEREF_Toc408472649\h9HYPERLINK\l"_Toc408472650"2.2分治算法的设计PAGEREF_Toc408472650\h9HYPERLINK\l"_Toc408472651"2.3动态规划算法的设计PAGEREF_Toc408472651\h10HYPERLINK\l"_Toc408472652"3算法实现PAGEREF_Toc408472652\h10HYPERLINK\l"_Toc408472653"3.2蛮力算法的实现PAGEREF_Toc408472653\h10HYPERLINK\l"_Toc408472654"3.2分治算法的实现PAGEREF_Toc408472654\h11HYPERLINK\l"_Toc408472655"3.3动态规划算法的实现PAGEREF_Toc408472655\h13HYPERLINK\l"_Toc408472656"4测试和分析PAGEREF_Toc408472656\h13HYPERLINK\l"_Toc408472657"4.1蛮力算法测试PAGEREF_Toc408472657\h13HYPERLINK\l"_Toc408472658"4.2蛮力算法时间复杂度的分析PAGEREF_Toc408472658\h15HYPERLINK\l"_Toc408472659"4.3分治算法测试PAGEREF_Toc408472659\h15HYPERLINK\l"_Toc408472660"4.4分治算法时间复杂度的分析PAGEREF_Toc408472660\h17HYPERLINK\l"_Toc408472661"4.5动态规划算法测试PAGEREF_Toc408472661\h17HYPERLINK\l"_Toc408472662"4.6动态规划算法时间复杂度的分析PAGEREF_Toc4084726