tsanmmmm2000's Tech Blog

Question

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

Thinking

此題最早是由布朗大學的Ulf Grenander教授所提出，我們可以參考Kadane's Algorithm來解

My C# Solution

public class Solution {
    public int MaxSubArray(int[] nums) {
        var maxEnding = nums[0];
        var maxSoFar = maxEnding;
        for (var i = 1; i < nums.Length; i++)
        {
            maxEnding = nums[i] > maxEnding + nums[i] 
                ? nums[i] 
                : maxEnding + nums[i];
            maxSoFar = maxSoFar > maxEnding ? maxSoFar : maxEnding;
        }
        return maxSoFar;
    }
}