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);
- }
结果截图
来源: http://www.bubuko.com/infodetail-1962710.html