careercup-中等难度 17.8

时间:2023-08-28 12:35:08

17.8 给定一个整数数组(有正数和负数),找出总和最大的连续序列,并返回总和。

解法:

就是求连续子序列的和最大,不过存在一个问题:

假设整个数组都是负数,怎么样才是正确的行为呢?看看这个简单的数组{-3,-10,-5},一下答案每个都可以说的通:

-3(假设子序列不能为空)

0(子序列的长度为空)

INT_MIN(视为错误的情况)

我们会选择第二种(maxSum=0),但并没有所谓的“正确”答案。这一点可以跟面试官好好讨论一番。

C++实现代码:

#include<iostream>
using namespace std; int getMaxSum(int a[],int n)
{
int sum=;
int maxSum=;
int i;
for(i=;i<n;i++)
{
sum+=a[i];
if(sum>maxSum)
maxSum=sum;
if(sum<)
sum=;
}
return maxSum;
} int main()
{
int arr[]={,-,-,,-,,,-,,};
cout<<getMaxSum(arr,)<<endl;
}