엔지니어 게시판
LeetCode 솔루션 분류

[Easy - wk2 - Q4] 53. Maximum Subarray

컨텐츠 정보

본문

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.

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.

관련자료

댓글 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.

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_subarray

mingki님의 댓글

  • 익명
  • 작성일
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.
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;
    }
};
전체 404 / 14 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 855 명
  • 오늘 방문자 5,154 명
  • 어제 방문자 6,932 명
  • 최대 방문자 14,831 명
  • 전체 회원수 1,481 명
알림 0