# Leetcode --- 53. Maximum Subarray

### Description:

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
:::warning
A subarray is a contiguous part of an array.
:::

:::info
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

:::



### 解法條列
1. 暴力解 O(n^2^)
2. 優化解 O(n)

### 解法細節

:::success

:::

### Python Solution
優化解

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = nums[0]
        for i in range(1, len(nums)):
            if(nums[i] + nums[i-1] > nums[i]):
                nums[i] += nums[i-1]
            if(nums[i]>ans):
                ans = nums[i]
        return ans

---

優化解 寫法2

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur = nums[0]
        ans = nums[0]
        for num in nums[1:]:
            cur = max(num, cur+num)
            ans = max(ans,cur)
        return ans

---

---

###### tags: `leetcode` `array` `easy` `homework`