要求:
1.输入一个整形数组，数组里有正数也有负数；
2.数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
3.求所有子数组的和的最大值。要求时间复杂度O（n）
设计思想：同背包问题；当前选中数组元素加上他前面那个数组元素，然后与自身比较，取大的那个数值，赋值给这个元素.然后进行遍历，最后求得的最大值便为所有子数组的和的最大值；//时间复杂度为O（n）
实现代码:
#include<iostream>
using namespace std;
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int main()
{
int a[100],i,n;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
for(i=2;i<=n;i++)
{
if(a[i]+a[i-1]>a[i])
a[i]=a[i]+a[i-1];
}
int ans=-100000;
for(i=1;i<=n;i++)
ans=max(ans,a[i]);
cout<<ans<<endl;
return 0;
}
运行结果截图:
