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

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

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

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

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

二、解題思路

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