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);
}

結果截圖