首页 > 代码库 > 最大子数组和

最大子数组和

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

最大子数组和