首页 > 代码库 > 求子数组的最大和
求子数组的最大和
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
1 #include <iostream> 2 /* 3 求子数组最大值 4 假设数组为a[]={1,-2,3,10,-4,7,2,-5} 5 可以依次想加，max保存最大值,temp保存当前的最大值 6 7 8 */ 9 using namespace std;10 int maxSum(int* a,int size)11 {12 int max=0,temp=0;13 for(int i=0;i<size;i++)14 {15 temp+=a[i];16 if(temp<0) //当小于0时，从新开始计算17 {18 temp=0;19 }20 if(temp>max)//当前值大于最大值时，把当前值赋值给最大值21 {22 max=temp;23 }24 }25 if(max==0) //如果数组的数据都是负数，则找出最大的负数值26 {27 max=a[0];28 for(int i=0;i<size;i++)29 {30 if(max<a[i])31 {32 max=a[i];33 }34 }35 }36 return max;37 }38 int main()39 {40 int a[]={1,-2,3,10,-4,7,2,-5},sum;41 sum=maxSum(a,8);42 cout<<sum;43 return 0;44 }
求子数组的最大和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。