问题描述:
给定长度为n的整数序列,a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大,或者求出最大的这个和。...如果该序列的所有元素都是负整数时定义其最大子段和为0。
例如(-2,11,-4,13,-5,2)的最大子段和为20,所求子区间为[2,4]。...问题分析:
最直接的想法就是利用遍历法遍历所有的可能,然后找到最大的那个,显然这不是一种有效的方法,但切实可行。...分治法:
针对最大字段和这个具体问题本身的结构,还可以从算法设计的策略上对上述O(n²)计算时间算法加以更深刻的改进。...则该给定序列的最大字段和有三种情行:
①和a[1..n/2]的最大字段和相同。
②和a[n/2+1:n]的最大字段和相同。