릿코드(LEETCODE)

53. Maximum Subarray

cepiloth 2020. 2. 13. 16:17
반응형

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

 

 

D 풀이

class Solution {
public:
    int maxSubArray(vector<int>& nums) {

        int sol = nums[0];
        vector<int> arr(nums.size());
        for (int i = 0; i < nums.size(); i++) {

            int cand = arr[i] = nums[i];
            for (int j = i+1; j < nums.size(); j++) {
                cand = cand + nums[j];
                arr[i] = max(cand, arr[i]);
            }
            sol = max(arr[i], sol);
        }

        return sol;
    }
};

class Solution {
public:
    int maxSubArray(vector<int>& nums) {

        int sol = nums[0];
        for (int i = 1; i < nums.size(); i++) {

            if(nums[i-1] + nums[i] > nums[i]) {
                nums[i] = nums[i-1] + nums[i];
            }
            sol = max(nums[i], sol);
        }

        return sol;
    }
};

 

W 풀이

class Solution {
public:
    int max(int a, int b) {
        return a > b ? a : b;
    }
    int maxSubArray(vector<int> &nums) {
        int size = nums.size();
        
        int cur = nums[0];
        int ans = cur;

        for (int i = 1; i < size; ++i) {
            int next = cur + nums[i];
            cur = max(next, nums[i]);  // cur=next : continue / cur=nums[i] : restart.
            ans = max(ans, cur);  // check current.
        }
        return ans;
    }
};

 

O 풀이

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

 

반응형