问题形容：
给定一只股票在某段时间内的历史价格变动曲线，找出一个可能实现收益最大化的时间段。
了解：
为找出最大化的收益，须要思考的是在买进和卖出时的价格变动幅度，因而从该股票的每日变动幅度来思考问题比拟适合。由此，能够将上述问题稍作变形：给定一只股票在某段时间内的每日变动幅度，找出一个适合的买进和卖出工夫，以实现收益最大化。因而，将输出数据转换如下，并试图在整个时间段中找到一个累加和最大的子区间，亦即最大子数组。
暴力求解办法：
首先可能想到的是在一个给定数组（区间）中，其子数组（子区间）的个数是C(2,n)，很容易就能遍历完所有子数组从而找出最大的那个，其最坏状况渐进工夫复杂度是(n2)。假如每日变动幅度保留在数组A中（A的下标从1到n），A.length示意A的元素个数，最终后果以元组模式返回；给出伪码如下：
BRUTE_FORCE(A) i = 1 sum = -infinity for i <= A.length, inc by 1 j = i last_sum = 0 for j <= A.length, inc by 1 last_sum += A[j] if last_sum > sum sum = last_sum start = i end = j return (start, end, sum)分治求解办法：
上述办法的渐进工夫复杂度差强人意。类比于归并排序，有时采纳分治策略可能取得更好的工夫复杂度。分治策略通常蕴含分解成子问题、解决子问题、合并子问题。由此能够推出大抵的解决思路：首先仍然假如数据输出如上一个办法那样，而后思考将A[1...n]拆分为规模大致相同的两个子数组left[1...mid]和right[mid+1...n]，其中mid=(1+n)/2向下取整，那么能够必定，最大子数组要么在这两个子数组中，要么横跨这两个子数组，因而能够别离求解这三种状况，取其中最大的子数组并返回即可。
对于left/right子数组可递归求解，而对于横跨两个子数组的状况，如果可能使得该状况下的求解工夫复杂度为O(n)，那么应该能让整体的最坏工夫复杂度低于(n2)。如果仅仅是通过遍历所有蕴含A[mid]和A[mid+1]的子数组来找最大子数组，那么很显然仅求解该状况就须要(n2)的工夫。能够推断横跨两个子数组的最大子数组，必须由两个别离在left/right中的子数组组成，这两个子数组在别离蕴含了A[mid]和A[mid+1]的所有子数组中是最大的；因为如果存在一个不满足上述条件的最大子数组，那么总能够用上述办法找到一个更大的子数组。
根据上述思路，很容易推知求解横跨两个子数组的状况只须要O(n)的工夫。由此给出伪码如下：
（1）子过程：找出横跨两个子数组的最大子数组
FIND_CROSSING_MAX_SUBARRAY(A, low, mid, high) left_sum = -infinity sum = 0 i = mid for i >= low, dec by 1 sum += A[i] if sum > left_sum left_sum = sum left_index = i right_sum = -infinity sum = 0 i = mid + 1 for i <= high, inc by 1 sum += A[i] if sum > right_sum right_sum = sum right_index = i return (left_index, right_index, left_sum+right_sum)（2）主过程：分治法找出最大子数组
FIND_MAX_SUBARRAY(A, low, high) if low == high return (low, high, A[low]) else mid = down_trunc((low + high) / 2) (left_start, left_end, left_sum) = FIND_MAX_SUBARRAY(A, low, mid) (right_start, right_end, right_sum) = FIND_MAX_SUBARRAY(A, mid+1, high) (cross_start, cross_end, cross_sum) = FIND_CROSSING_MAX_SUBARRAY(A, low, mid, high) if left_sum > right_sum and left_sum > cross_sum return (left_start, left_end, left_sum) else if right_sum > left_sum and right_sum > cross_sum return (right_start, right_end, right_sum) else return (cross_start, cross_end, cross_sum)能够看出上述算法渐进工夫复杂度为(nlg(n))。
缩减问题规模的办法：
在查找过程中，是否能够依据现有的信息，来缩减须要排查的子数组个数，进而取得更好的工夫复杂度呢？一个思路是不再反复查看以前累加过的元素，即从左至右累加元素，保留其中的最大子数组，如果在退出一个元素后累加和为正数，则从该元素的后一个元素从新累加，直至整个数组遍历结束。该思路无效的前提是证实以下几个假如：
- 能够将最大子数组起源分为三种：曾经遍历完的数组局部、未遍历的数组局部以及逾越这两局部的子数组
- 能够假如当从左至右累加直至累加和为负，所得的最大子数组是以后已遍历完的数组局部中最大的
- 能够假如当累加和为负时，潜在的最大子数组不可能从该元素或该元素右边的元素开始
假如1不证自明。
假如从A[1]累加到A[i]时第一次遇到其累加和为负（1<=i<=n），那么A[i]肯定为负，且A[1]+...+A[i-1]>=0。当i<=2时，显然此时假如2成立。当i>2时，能够认为在A[1]...A[i]中，所有子数组可分为三种：从A[1]开始向右拓展、从A[i]开始向左拓展以及不蕴含A[1]和A[i]的两头子数组；显然从A[i]向左拓展的不可能是最大子数组，而如果不蕴含A[1]和A[i]的两头子数组是最大子数组，那么能够使该两头子数组加上其右边的局部形成一个新的子数组，而且该子数组总是大于等于这个两头子数组，因为其右边局部总是大于等于0，所以该状况下假如2也得证。综合来看假如2是成立的。
对于假如3，显然潜在的最大子数组不可能从A[i]开始，因为A[i]<0。当潜在的最大子数组从A[i]的右边开始时，假如其从A[j]开始（1<=j<i）。显然j不能等于1，因为A[1]+...+A[i]<0；当j>1时，A[j]+...+A[i]肯定是正数，因为A[1]+...+A[j-1]肯定大于等于0而A[1]+...+A[i]肯定为负。所以综合来看，从A[i]或者A[i]的右边寻找潜在的子数组是没有意义的。
伪码如下，工夫复杂度为(n)。对于全副是正数的状况，非凡解决即可，不影响工夫复杂度。
LINEAR_SEARCH_MAX_SUBARRAY(A) sum = -infinity start = 0 end = 0 cur_sum = 0 cur_start_index = 1 i = 1 for i <= A.length, inc by 1 cur_sum += A[i] if cur_sum < 0 cur_sum = 0 cur_start_index = i + 1 else if sum < cur_sum sum = cur_sum start = cur_start_index end = i return (start, end, sum)