릿코드(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;
}
};
반응형