30.連續子數組的最大和

一、題目描述

HZ偶爾會拿些專業問題來忽悠那些非計算機專業的同學。今天測試組開完會後,他又發話了:在古老的一維模式識别中,常常需要計算連續子向量的最大和,當向量全為正數的時候,問題很好解決。但是,如果向量中包含負數,是否應該包含某個負數,并期望旁邊的正數會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續子向量的最大和為8(從第0個開始,到第3個為止)。你會不會被他忽悠住？(子向量的長度至少是1)

二、思路

首先，我們會想到用兩個數來輔助存儲目前的最大和，定義兩個變量res和sum，res用來記錄目前的最大和，sum用來記錄目前的和，如果sum大于res，則更新res。這一步想好之後，接下來就是周遊數組，我們最容易想到的就是使用雙層循環來周遊數組，以便找到從任意位置開始的連續子數組的最大和，但是，如果仔細想想，其實，我們隻對數組周遊一次，也是能夠找到連續子數組的最大和的，下面是兩種方法的代碼實作。

方法一：使用雙層循環，時間複雜度O(n^2)

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int res = array[];
        for (int i = ; i < array.length; i++){
            int sum = ;
            for (int j = i; j < array.length; j++){
                sum += array[j];
                if (sum > res)
                    res = sum;
            }
        }
        return res;
    }
}
           

方法二：單層循環，在方法一中，如果數組第i個元素為負數，那麼我們其實是沒有必要進行i元素以後的周遊的，因為，負數總會讓和變小，既然要變小，我們為什麼還要這一次周遊呢？是以就有下面的改進方法。

/**
*改進版，周遊一次數組即可,時間複雜度O(n)。
*用兩個變量來進行記錄，一個用于加和，一個用于記錄最大和。
**/
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if (array.length ==  || array == null)
            return ;
        int res = array[];
        int sum = ;
        for (int i = ; i < array.length; i++){
            if (sum < ){
                sum = array[i];//因為加一個負數肯定會使結果小于array[i]，是以直接舍去負數
            } else {
                 sum += array[i];
            }
            if (sum > res)
                res = sum;
        }
        return res;
    }
}
           

該題目的變形：求使出現最大和的子數組；

思路：用兩個标簽分别記錄子數組開始和結束的位置，如果使用for雙層循環的話，當出現新的最大值時，分别記錄i和j的值，下面是另一種循環求解：

/*
     * 1.找出出現最大連續和的子數組
     * 當數組有正有負時，i=0周遊數組，從大于0的那個元素開始，記錄此時的下标為shart（最大子數組起始下标），從start開始周遊剩下的元素，若元素和num大于max的值則更新max，
     * 且将此時的下标指派給end（最大子數組終止下标），當num小于0則說明後面出現的（如果出現）最大子數組不可能包含這些元素，是以退出内層循環，繼續外層循環，找下一個大于
     * 0的數組元素，且外層循環的i變量此時變為temp+1，繼續下面的循環。注意内層循環當temp>=length時，說明内層循環已經把所有數組元素都周遊結束，是以外層循環可以直接break。
     */
    public static ArrayList<Integer> findGreatestSumArrayOfSubArray(int arr[]) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int i = ;
        int temp = ;
        int num = ;
        int max = ;
        int start = ;
        int end = ;
        int flag = ;//用來判斷數組中是否全為負，如果flag = arr.length,則全為負數
        while (i < arr.length){ //第一層循環，從大于零的元素位置開始，并記錄開始下标，
            if (arr[i] > ){
                temp = i;
                start = i;
                while (temp < arr.length){ //第二層循環，用temp做臨時變量，找最大值，并記錄最大值結束下标
                    num += arr[temp];
                    if (num < ){
                        num = ;
                        i = temp + ;
                        break;
                    }
                    if (num > max){
                        max = num;
                        end = temp;
                    }
                    temp++;
                }
                if(temp >= arr.length) //避免在外層循環中陷入死循環，因為此時i不一定等于數組長度，i值不增，外層循環則停不下來。
                    break;
            }
            else {
                i++;
                flag++;
            }
        }
        if (flag == arr.length) //如果元素全為負，則輸出空數組
            return list;
        else {
            for (int j = start; j<= end; j++)
                list.add(arr[j]);
        }
        return list;
    }