-
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