# 【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.

> 給一個整數陣列nums，找到它所有的子陣列(至少要有一個數字)中，總和最大可以為多少。

## Example:

Example:

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

## Solution

* 解法一：divide and conquer approach.
* 解法二：解法一的遞迴直接化成iterator的寫法，拆成自己和自己前一個的最大值。
* 一開始沒看到至少要有一個數字，多打了幾段code反而是錯的...

### Code

* 解法一：

//我還沒寫

* 解法二：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.size()==0)return 0;
        
        int ans=nums[0];
        for(int i=1;i<nums.size();i++)
        {
            nums[i]=max(nums[i],nums[i]+nums[i-1]);
            ans = max(ans,nums[i]);
        }
        return ans;
    }
};

###### tags: `LeetCode` `C++`