###### tags: `Leetcode` `easy` `dynamic programming` `greedy` `python` `c++`

# 53. Maximum Subarray

## [題目來源:] https://leetcode.com/problems/maximum-subarray/

## 題目:
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.**

**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

## 解題想法:
* 進階題目:[152. Maximum Product Subarray](/RSZktS2hQnCK2uwNKXJZFA)
* 此題為求連續累加最大
* 若前一個總合為負，則忽略了
* 若為正，表是加上現在(正or負都不管)還有變大的希望

## Python:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #dp只考慮前面:
        #若前面總合為負:放棄
        #為正:加上當前
        res=nums[0]
        for i in range(1,len(nums)):
            if nums[i-1]>0:
                nums[i]+=nums[i-1]
            res=max(res,nums[i])
        return res
    
if __name__ == '__main__':
    nums = [5,4,-1,7,8]
    result = Solution()
    result = result.maxSubArray(nums)
    print(result)
    
'''
        #greedy
        cur_max=nums[0]
        total_max=nums[0]
        for i in range(1,len(nums)):
            cur_max=max(nums[i],cur_max+nums[i])
            total_max=max(total_max,cur_max)
        return total_max
'''

## C++:

#include<iostream>
#include<vector>
using namespace std;
//dp
class Solution{
public :
    int maxSubArray(vector<int>& nums){
        int res=nums[0];
        for (int pos=1; pos<nums.size(); pos++){
            if (nums[pos-1]>0)
                nums[pos]+=nums[pos-1];
            res=max(res,nums[pos]);
        }
        return res;
    }
};
//greedy
class Solution2{
public:
    int maxSubArray(vector<int>& nums){
        int total_max=nums[0];
        int cur_max=nums[0];
        for(int i=1; i<nums.size(); i++){
            cur_max=max(cur_max+nums[i],nums[i]);
            total_max=max(total_max,cur_max);
        }
        return total_max;
    }
};

int main(){
    Solution res;
    vector<int> nums={-2,1,-3,4,-1,2,1,-5,4};
    int ans=res.maxSubArray(nums);
    cout<<ans<<endl;


    Solution2 res2;
    vector<int> nums2={-2,1,-3,4,-1,2,1,-5,4};
    int ans2=res2.maxSubArray(nums2);
    cout<<ans2<<endl;
    return 0;
}