11/3 (금) 합이 가장 큰 부분 배열 TIL

공부한 것

• LeetCode #53. Maximum Subarray

  Maximum Subarray - LeetCode

  Can you solve this real interview question? Maximum Subarray - Given an integer array nums, find the subarray with the largest sum, and return its sum.   Example 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has the largest sum 6. Example 2: Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1. Example 3: Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 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.

  https://leetcode.com/problems/maximum-subarray/description/

  

  • 가장 신기하고 간결하다고 생각된 풀이를 첨부한다.
  • 해답 코드:

    // Time complexity: O(N)
    // Space complexity: O(1) 
    function maxSubArray3(nums: number[]): number {
    	let localSum = 0;
    	let maxSum = -Infinity;
    
    	for (const num of nums) {
    		// 지금 수와 지금 수를 부분 합계에 더한 값 중 더 큰 쪽을 새로운 부분 합계로 삼는다. 
    		localSum = Math.max(num, localSum + num);
    		// 만약 새로운 부분 합계가 최고 합계보다 더 크면 최고 합계를 업데이트한다. 
    		if (localSum > maxSum) {
    			maxSum = localSum;
    		}
    	}
    
    	return maxSum;
    }

Uploaded by N2T