劍指Offer面試題：28.連續子數組的最大和

題目：輸入一個整型數組，數組裡有正數也有負數。數組中一個或連續的多個整數組成一個子數組。求所有子數組的和的最大值。要求時間複雜度為O(n)。例如輸入的數組為{1,-2,3,10,-4,7,2,-5}，和最大的子數組為{3,10,-4,7,2}，是以輸出為該子數組的和18。

一、題目：連續子數組的最大和

　　這個題目在我去年參加校園招聘時，某公司的二面采用了機試，而題目剛好就是這道題。一般看到這道題目就會想到枚舉出數組的所有子數組并求出它們的和。一個長度為n的數組，總共有n(n+1)/2個子數組。計算出所有子數組的和，最快也需要O(n2)的時間。但是最直覺的方法不會是最優的解法，是以面試官不會滿意這樣的思路。

二、解題思路

2.1 核心步驟

　　Step1.從頭到尾逐個累加數組中的每個數字，初始化和為0；（nCurrSum=0，nGreatestNum=int.MinValue）

　　Step2.首先加上第一個數字，從第二個數字開始累加，依次将累加和儲存到一個臨時變量（nCurrSum）中；

　　Step3.如果目前累加和（nCurrSum）小于0，那抛棄前面的子數組和，從下一個數字開始重新累加；相反，則将目前累加和（nCurrSum）與傳回累加和（nGreatestNum）進行比較，如果nCurrSum>nGreatestNum，則更新nGreatestNum。

　　這樣比較進行一次周遊之後，就可以得到最終的最大累加和，時間複雜度是O(n)。下圖展示了計算數組{1,-2,3,10,-4,7,2,-5}中子數組的最大和的過程：

2.2 代碼實作

/// <summary>
    /// 計算連續子數組的最大和
    /// </summary>
    public static int FindGreatestSumOfSubArray(int[] array, out bool isValidInput)
    {
        if (array == null || array.Length <= 0)
        {
            isValidInput = false;
            return 0;
        }

        isValidInput = true;

        int currSum = 0;
        int greatestSum = int.MinValue;

        for (int i = 0; i < array.Length; i++)
        {
            if(currSum <= 0)
            {
                currSum = array[i];
            }
            else
            {
                currSum += array[i];
            }

            if (currSum > greatestSum)
            {
                greatestSum = currSum;
            }
        }

        return greatestSum;
    }      

三、單元測試

3.1 測試用例

// 1, -2, 3, 10, -4, 7, 2, -5
    [TestMethod]
    public void GetGreatestNumTest1()
    {
        int[] data = { 1, -2, 3, 10, -4, 7, 2, -5 };
        bool isValid = true;
        int actual = SubArrayHelper.FindGreatestSumOfSubArray(data, out isValid);
        if (isValid)
        {
            Assert.AreEqual(actual, 18);
        }
        else
        {
            Assert.AreEqual(isValid, false);
        }
    }

    // 所有數字都是負數
    // -2, -8, -1, -5, -9
    [TestMethod]
    public void GetGreatestNumTest2()
    {
        int[] data = { -2, -8, -1, -5, -9 };
        bool isValid = true;
        int actual = SubArrayHelper.FindGreatestSumOfSubArray(data, out isValid);
        if (isValid)
        {
            Assert.AreEqual(actual, -1);
        }
        else
        {
            Assert.AreEqual(isValid, false);
        }
    }

    // 所有數字都是正數
    // 2, 8, 1, 5, 9
    [TestMethod]
    public void GetGreatestNumTest3()
    {
        int[] data = { 2, 8, 1, 5, 9 };
        bool isValid = true;
        int actual = SubArrayHelper.FindGreatestSumOfSubArray(data, out isValid);
        if (isValid)
        {
            Assert.AreEqual(actual, 25);
        }
        else
        {
            Assert.AreEqual(isValid, false);
        }
    }

    // 無效輸入
    [TestMethod]
    public void GetGreatestNumTest4()
    {
        bool isValid = true;
        int actual = SubArrayHelper.FindGreatestSumOfSubArray(null, out isValid);
        if (isValid)
        {
            Assert.AreEqual(actual, 0);
        }
        else
        {
            Assert.AreEqual(isValid, false);
        }
    }      

3.2 測試結果

　　（1）測試用例通過情況

　　（2）代碼覆寫率

作者：周旭龍

出處：http://edisonchou.cnblogs.com

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連結。