LeetCode 솔루션 분류
[Easy - wk2 - Q4] 53. Maximum Subarray
본문
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = [1] Output: 1
Example 3:
Input: nums = [5,4,-1,7,8] Output: 23
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
태그
#leetcode, #문제풀이, #easy, #linkedin, #amazon, #apple, #microsoft, #adobe, #google, #facebook, #cisco, #jpmorgan, #shopee, #bloomberg, #uber, #vmware, #oracle, #saleforce, #bytedance, #docusign, #samsung, #goldman sachs, #servicenow, #walmart global tech, #paytm, #inforsys, #array, #divide and conquer, #dynamic p
관련자료
댓글 4
Jack님의 댓글
- 익명
- 작성일
python
Runtime: 892 ms, faster than 55.24% of Python3 online submissions for Maximum Subarray.
Memory Usage: 28.7 MB, less than 10.09% of Python3 online submissions for Maximum Subarray.
Runtime: 892 ms, faster than 55.24% of Python3 online submissions for Maximum Subarray.
Memory Usage: 28.7 MB, less than 10.09% of Python3 online submissions for Maximum Subarray.
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1,len(nums)):
nums[i] += nums[i-1] if nums[i-1] > 0 else 0
return max(nums)Jack님의 댓글
- 익명
- 작성일
Java
class Solution {
public int maxSubArray(int[] nums) {
// Initialize our variables using the first element.
int currentSubarray = nums[0];
int maxSubarray = nums[0];
// Start with the 2nd element since we already used the first one.
for (int i = 1; i < nums.length; i++) {
int num = nums[i];
// If current_subarray is negative, throw it away. Otherwise, keep adding to it.
currentSubarray = Math.max(num, currentSubarray + num);
maxSubarray = Math.max(maxSubarray, currentSubarray);
}
return maxSubarray;
}
}Jack님의 댓글
- 익명
- 작성일
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
# Initialize our variables using the first element.
current_subarray = max_subarray = nums[0]
# Start with the 2nd element since we already used the first one.
for num in nums[1:]:
# If current_subarray is negative, throw it away. Otherwise, keep adding to it.
current_subarray = max(num, current_subarray + num)
max_subarray = max(max_subarray, current_subarray)
return max_subarraymingki님의 댓글
- 익명
- 작성일
C++
Runtime: 120 ms, faster than 81.28% of C++ online submissions for Maximum Subarray.
Memory Usage: 67.7 MB, less than 91.16% of C++ online submissions for Maximum Subarray.
Runtime: 120 ms, faster than 81.28% of C++ online submissions for Maximum Subarray.
Memory Usage: 67.7 MB, less than 91.16% of C++ online submissions for Maximum Subarray.
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSum = -1e9;
int currSum = -1e9;
int n = nums.size();
for (int i = 0; i < n; ++i) {
currSum = max(currSum + nums[i], nums[i]);
maxSum = max(maxSum, currSum);
}
return maxSum;
}
};
