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);}

结果截图