1、问题描述
成都创新互联公司拥有网站维护技术和项目管理团队，建立的售前、实施和售后服务体系，为客户提供定制化的做网站、成都做网站、网站维护、温江服务器托管解决方案。为客户网站安全和日常运维提供整体管家式外包优质服务。我们的网站维护服务覆盖集团企业、上市公司、外企网站、购物商城网站建设、政府网站等各类型客户群体，为全球超过千家企业提供全方位网站维护、服务器维护解决方案。
在数组中，有正数，负数，0，求其最大子数组和？
算法思想：穷举的解法，找出所有的子数组和，利用3层for循环；
去冗余--->贪心算法，将小于0的子数组直接淘汰，因为之前已经保存过最大子数组值了；
2、暴力破解
#include//求最大子数组和，暴力破解法，时间复杂度：O(n^3) int maxSubArray(int *a, int n); int maxSubArray(int *a, int n){ int i; int j; int k; int ans = -100000000; for(i = 0; i < n; i++){ for(j = i; j < n; j++){ int sum = 0; for(k = i; k <= j; k++){ sum += a[k]; } if(sum > ans){ ans = sum; } } } return ans; } void main(void){ int a[] = {1, -2, -3, 3, 5, 6, -1}; int count = sizeof(a)/sizeof(int); int maxNumber; maxNumber = maxSubArray(a, count); printf("%d\n", maxNumber); }
结果截图
3、贪心算法
#include//最大子数字和：贪心算法,时间复杂度为：O(n) int maxSubArray(int *a, int n); int maxSubArray(int *a, int n){ int i; int ans = -10000000; int sum = 0; for(i = 0; i < n; i++){ sum += a[i]; if(sum > ans){ ans = sum; //保存先前的最大值 } if(sum < 0){ sum = 0; //将一部分和<0的直接删去 } } return ans; } void main(void){ int a[] = {-1, -2, 3, 6, -6, 3, 3, 2, -3}; int count = sizeof(a)/sizeof(int); int maxNumber; maxNumber = maxSubArray(a, count); printf("%d\n", maxNumber); }
结果截图
