본문 바로가기
프로그래밍/LeetCode

C++ 53. Maximum Subarray(Leet Code)

by devsu 2020. 6. 8.

Leet Code_53. Maximum Subarray

Dynamic Programming

 

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

 

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

SubArray중 합계가 큰 값을 리턴

방법

1. SubArray중 합계가 큰 값을 리턴

 

결과

SubArray중 합계가 큰 값을 리턴

 

통과한 코드

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