2.3

2.3-7

4

4.1 最大子数组问题

最大子数组

数组A的和最大的非空连续子数组 我们称这样的连续子数组为最大子数组

使用分治策略的解决方法

Find-Max-Crossing-Subarray(a,low,mid,high)

left-sum = -∞
sun = 0
for i = mid downto low
	sum = sum + A[i]
    if sum > left-sum
    	left sum = sum
        max-left = i
right-sum = -∞
sun = 0
for j = mid + 1 to high
	sum = sum + A[j]
    if sum > right-sum
    	right sum = sum
        max-right = j
return (max-left,max-right,left-sum + right-sum)

4.1-5

4-1

6

6.3

6.3-3

8

8.1

8.1-3

8.3

8.3-4

8.4

8.4-2

9

9.3

9.3-3