Cracking the coding interview--Q19.7

February 22, 2013
作者:Hawstein
出处:http://hawstein.com/posts/19.7.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

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。

此外,我们可以用一个全局变量来标示非法输入。代码如下:

#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