最大子数组和
1、问题描述
在数组中,有正数,负数,0,求其最大子数组和?
算法思想:穷举的解法,找出所有的子数组和,利用3层for循环;
去冗余--->贪心算法,将小于0的子数组直接淘汰,因为之前已经保存过最大子数组值了;
2、暴力破解
#include<stdio.h>//求最大子数组和,暴力破解法,时间复杂度:O(n^3)intmaxSubArray(int*a,intn);intmaxSubArray(int*a,intn){inti;intj;intk;intans=-100000000;for(i=0;i<n;i++){for(j=i;j<n;j++){intsum=0;for(k=i;k<=j;k++){sum+=a[k];}if(sum>ans){ans=sum;}}}returnans;}voidmain(void){inta[]={1,-2,-3,3,5,6,-1};intcount=sizeof(a)/sizeof(int);intmaxNumber;maxNumber=maxSubArray(a,count);printf("%d\n",maxNumber);}
结果截图
3、贪心算法
#include<stdio.h>//最大子数字和:贪心算法,时间复杂度为:O(n)intmaxSubArray(int*a,intn);intmaxSubArray(int*a,intn){inti;intans=-10000000;intsum=0;for(i=0;i<n;i++){sum+=a[i];if(sum>ans){ans=sum;//保存先前的最大值}if(sum<0){sum=0;//将一部分和<0的直接删去}}returnans;}voidmain(void){inta[]={-1,-2,3,6,-6,3,3,2,-3};intcount=sizeof(a)/sizeof(int);intmaxNumber;maxNumber=maxSubArray(a,count);printf("%d\n",maxNumber);}
结果截图
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。