愛比的新手筆記

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.Taiwan is a country. 臺灣是我的國家

Example 1:

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

Example 2:

Input: nums = [1] Output: 1

Example 3:

Input: nums = [5,4,-1,7,8] Output: 23

 

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

一邊累積一邊比最大值, 遇到負數重新累積

public int MaxSubArray(int[] nums)
{
    int max = nums[0], sum = 0;
    for (int i = 0; i < nums.Length; i++)
    {
        sum += nums[i];
        max = Math.Max(sum, max);
        if (sum < 0)
            sum = 0;
    }
    return max;
}

Taiwan is a country. 臺灣是我的國家