//输入一个整形数组。有整数也有负数，数组中连续一个或多个子数组，每一个子数组都有一个和，求全部子数组的和的最大值，要求时间复杂度O(n)
#include<iostream> int GetMax( int * arr)
{
int max = arr[0];
for (int i = 1; i < 10; i++)
{
if (max < arr[i])
{
max = arr[i];
}
} return max;
} int getMaxSum(int * arr)
{
int result = 0;
int tmp = 0;
for (int i = 0; i < 10; i++)
{
if (tmp>0)
{
tmp += arr[i];
}
else
{
tmp = arr[i];
}
if (tmp > result)
result = tmp; } return result;
} using namespace std; void main()
{
int arr[10] = { 1, -3, 8, -6, 2, -3,4, 8, -11, 12 };
int max = GetMax( arr);
if (max <= 0)
{
cout << "最大子数组和为" << max;
cin.get();
return;
}
int result = getMaxSum(arr); cout << "最大子数组和为" << result; cin.get();
}
