题目
原文：
You are given an array of integers (both positive and negative). Find the continuous sequence with the largest sum. Return the sum.
EXAMPLE
Input: {2, -8, 3, -2, 4, -10}
Output: 5 (i.e., {3, -2, 4} )
译文：
给出一个整数数组(包含正数和负数)，找到和最大的连续子序列，返回和。
例子：
输入: {2, -8, 3, -2, 4, -10}
输出: 5 (即, {3, -2, 4} )
解答
经典的面试题目，遍历一遍数组，用变量maxsum保存遍历过程中的最大和， 用变量cursum保存遍历过程中的当前和。在遍历的过程中，我们只需要做3件事， 第一：如果当前和cursum小于等于0，说明前面的连续和不会对后面的连续和产生贡献， 要么使后面的连续和减少，要么不变。因此舍弃cursum，用当前的元素更新它。 第二：如果当前和cursum是大于0的，累加当前元素。第三：如果当前和cursum 大于最大和maxsum，则更新最大和maxsum。
此外，我们可以用一个全局变量来标示非法输入。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
using namespace std;
bool g_Invalid = false;
int GetMaxSum(int a[], int n){
if(a==NULL || n<=0){
g_Invalid = true;
return 0;
}
g_Invalid = false;
int max_sum = 1<<31; // Min Int
int cur_sum = 0;
for(int i=0; i<n; ++i){
if(cur_sum <= 0)
cur_sum = a[i];
else
cur_sum += a[i];
if(cur_sum > max_sum)
max_sum = cur_sum;
}
return max_sum;
}
int main(){
int a[] = {
2, -8, 3, -2, 4, -10
};
int max_sum = GetMaxSum(a, 6);
if(g_Invalid)
cout<<"Invalid Input!"<<endl;
else
cout<<max_sum<<endl;
return 0;
}
注意：当数组中的数全为负，上述程序输出的是数组中最大的负数，子序列长度为1。 这里可以和面试官进行交流，子序列长度是否可以为0，即当数组中的数全为负时， 我们输出的答案是0，子序列长度为0。
全书题解目录：
Cracking the coding interview–问题与解答
全书的C++代码托管在Github上：
https://github.com/Hawstein/cracking-the-coding-interview
声明：自由转载-非商用-非衍生-保持署名 | 创意共享3.0许可证，转载请注明作者及出处
出处：http://hawstein.com/2013/02/22/19.7/
