**问题: **
已知有一组整数组成的数组 (随机包含正数和负数) ，其中数字是乱序排列的，请找出其中最大和的子数组。
例如：
对于数组 -2, 1, -3, 4, -1, 2, 1, -5, 4， 其最大和的子数组是4, ?1, 2, 1, 而和是 6。
**解答: **
这是一道非常受欢迎的技术面试题，最佳解决方案是使用时间复杂度是 O(n)的 Kadane算法，关于Kadane算法的请点击这里.
整体思路是从前向后扫描数组并随时计算截止到当前下标(Index) 最大和的子数组, 核心公式就是：
<blockquote>
maxSum(i+1) = max(maxSum(i)+ [i], [i])
</blockquote>
下面是求解最大和值算法的伪代码：
<code>
def max_subarray(A):
//预防数组为空
max_ending_here = max_so_far = A[0]
for x in A[1:]:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
//返回最大的和
return max_so_far
</code>
下面是上述算法的Swift版：
<code>
func maxSum(intArray: [Int]) -> Int {
var maxEndingHere = intArray[0]
var maxSoFar = intArray[0]
for item in intArray {
let temp = maxEndingHere + item
if temp > item {
maxEndingHere = temp
} else {
maxEndingHere = item
}
if maxEndingHere > maxSoFar {
maxSoFar = maxEndingHere
}
}
return maxSoFar
}
let intArray = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
let result = maxSum(intArray)
result = 6
</code>
因为数组内有可能包含负数，最大和子数组是有可能含有负数的。
如果需要求子数组的开始下标和结束下标， 下面是对上述算法的改进：
<code>void maxSumSubArray( Array array, int start, int end, int maxSum ){
// maxSumSoFar给最小值，因为数组内可能有负数
int maxSumSoFar = -2147483648;
int curSum = 0;
int a = b = s = i = 0;
for( i = 0; i < array.length; i++ ) {
//当前最大和 + 当前下标的值
curSum += array[i];
if ( curSum > maxSumSoFar ) {
maxSumSoFar = curSum;
//s 是子数组开始下标
a = s;
//b 是子数组结束下标
b = i;
}
//如果curSum小于0， 需要重设curSum的值和开始下标
if( curSum < 0 ) {
curSum = 0; s = i + 1;
}
}
start = a;
end = b;
maxSum = maxSumSoFar;
}</code>
思考题：
已知有一组整数组成的数组 (随机包含正数和负数) ，其中数字是乱序排列的，请找出其中最大乘积的子数组。
<blockquote> 如果你真的看懂了，请点赞。 </blockquote>
推荐阅读
