最大子数组问题

假设有一个n长度的数组, 求数组中最大的非空子数组.即子数组各个元素相加之和最大

思路1

使用分治策略求解, 找到数组的中间位置mid, 定义两边位置为left, right;

在A[left, right] 中 要求解的子数组必然是以下三种情况之一:

1.最大连续子数组在 A[left, mid] 的子数组中

2.最大连续子数组在 A[mid+1, right] 的子数组中

3.最大连续子数组A[i, j]; 包含了A[mid],即 left <= i <= mid <= j <= right.

思路2 

设置DP数组, DP[i]表示数组 A[x, i]为当前从[left, i]的最大连续子数组, left <= x <= i;

当我们把第i+1个元素加入整个数组中时, 考虑DP[i]是否大于0, 如果是则DP[i+1]=DP[i]+A[i+1];

否则应当舍弃前面相加结果, 重新计算最大连续子数组即DP[i+1] = A[i+1];

这时算法时间复杂度为O(n);