算法导论第4章思考题
4.1-5 使用如下思想为最大子数组问题设计一个非递归、线性时间的算法。由左至右处理数组，记录到目前为止已经处理过的最大子数组。若已知A[1…j]的最大子数组，基于如下性质将解扩展为A[1…j+1]的最大子数组：A[1…j+1]的最大子数组要么是A[1…j]的最大子数组，要么是某个子数组A[i…j+1](1 ⩽ \leqslant ⩽i ⩽ j + 1 ) \leqslant j+1) ⩽j+1)
func(A)n = A.lengthmax-sum = -∞sum = -∞for j = 1 to ncurrentHigh = jif sum > 0sum = sum + A[j]elsecurrentLow = jsum = A[j]if sum > max-summax-sum = sumlow = currentLowhigh = currentHighreturn (low, high, max-sum)