ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 53. Maximum Subarray
    릿코드(LEETCODE) 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;
        }
    };

     

    반응형

    '릿코드(LEETCODE)' 카테고리의 다른 글

    1346. Check If N and Its Double Exist  (0) 2020.02.14
    1025. Divisor Game  (0) 2020.02.14
    392. Is Subsequence  (0) 2020.02.13
    342. Power of Four  (0) 2020.02.13
    1290. Convert Binary Number in a Linked List to Integer  (0) 2020.02.13

    댓글

Designed by Tistory.