首页 > 代码库 > 最大子数组和
最大子数组和
1、问题描述
在数组中,有正数,负数,0,求其最大子数组和?
算法思想:穷举的解法,找出所有的子数组和,利用3层for循环;
去冗余--->贪心算法,将小于0的子数组直接淘汰,因为之前已经保存过最大子数组值了;
2、暴力破解
#include<stdio.h> //求最大子数组和,暴力破解法,时间复杂度: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<stdio.h> //最大子数字和:贪心算法,时间复杂度为: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); }
结果截图
本文出自 “wait0804” 博客,请务必保留此出处http://wait0804.blog.51cto.com/11586096/1901876
最大子数组和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。