最大子數(shù)組和

1、問題描述

  在數(shù)組中，有正數(shù)，負(fù)數(shù)，0，求其最大子數(shù)組和？

  算法思想：窮舉的解法，找出所有的子數(shù)組和，利用3層for循環(huán)；

  去冗余--->貪心算法，將小于0的子數(shù)組直接淘汰，因?yàn)橹耙呀?jīng)保存過最大子數(shù)組值了；

2、暴力破解

#include<stdio.h>

//求最大子數(shù)組和，暴力破解法，時(shí)間復(fù)雜度：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);
}

結(jié)果截圖

3、貪心算法

#include<stdio.h>

//最大子數(shù)字和：貪心算法,時(shí)間復(fù)雜度為：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);
}

結(jié)果截圖