leetcode(리트코드)53-Maximum Subarray

leetcode 53 - Maximum Subarray 문제입니다.

1. 문제

https://leetcode.com/problems/maximum-subarray/

---

2. Input , Output

Constraints:

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

---

3. 분류 및 난이도

Hard 난이도 문제입니다.
leetcode Top 100 Liked의 문제입니다.

---

4. 문제 해석

• 주어진 배열내에서 연속된 수를 더해 가장큰 값을 찾습니다.
• DP로 풀었습니다.

---

5. code

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

---

6. 결과 및 후기, 개선점

0ms 코드와 같습니다.