[LeetCode演算法 #53] 圖解 Maximum Subarray (Sliding Window)

題目

先來看 53. Maximum Subarray 的題目內容：

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

解題思路

從陣列第一個元素開始加總，如果加總的結果小於當前元素，則以當前元素為新的加總開頭，並暫存結果。

public class Solution {
    public int MaxSubArray(int[] nums) {
        int maxResult= nums[0];
        int maxInternal= nums[0];
        for(int i =1 ; i < nums.Count()  ;i++){
            maxInternal= nums[i] > maxInternal + nums[i] ? nums[i] : maxInternal + nums[i];
            maxResult = maxResult > maxInternal ? maxResult : maxInternal;
        }
        return maxResult;
    }
}