题目
输入一个整型数组，数组里有正数也有负数。 数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。 求所有子数组的和的最大值。要求时间复杂度为O(n)。 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
代码
#include<iostream>
using namespace std;
#define NUM 8
int main()
{
int ary[NUM] = { 1, -2, 3, 10, -4, 7, 2, -5 };
int max = 0;//保存最大和
int curSum = 0;//保存当前和
int curStart = 0;//当前和的起始位置
int start = 0;//最大和的起始位置
int end = 0;//最大和的终止位置
for (int i = 0; i<NUM; i++)
{
if (i == 0)
{
curSum = max = ary[i];
continue;
}
if (curSum<0)
{
curSum = 0;//与负数相加，和会减小，所以抛弃以前的和
curStart = i;
}
//最大值已经被保存下来，所以请大胆的继续往前加
curSum += ary[i];
//当前和被保存为最大值，记录下它的起始位置和结束位置
if (curSum>max)
{
max = curSum;
start = curStart;
end = i;
}
}
cout << "和最大的子数组为：" << endl;
for (int i = start; i <= end; i++)
{
cout << ary[i] << " ";
}
cout << "= " << max;
cin.get();
return 0;
}
结果
结果.png
