Maximum Subarray

Link

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

Deadline

Oct 12, 2021

Status

Archived

Type

dynamic programming

📄문제

✏️풀이

은찬


const maxSubArray = (nums) => {
    const dp = Array.from({length: nums.length}, () => 0);
    let answer = -1000000;
    
    dp[0] = nums[0];
    
    for(let i = 0; i < nums.length; i++){
        dp[i] = nums[i] < dp[i - 1] + nums[i] ? dp[i - 1] + nums[i] : nums[i];
        answer = answer < dp[i] ? dp[i] : answer;
    }
    
    return answer;
};

재영


var maxSubArray = function(nums) {
    const arr = new Array(nums.length).fill(0);
    nums.forEach((num, idx) => 
			arr[idx] = idx 
				? Math.max(num, num + arr[idx - 1]) 
				: num
		) 
    return Math.max(...arr)
};

희진

시간 초과 204/209


var maxSubArray = function(nums) {
    let sum;
    let maxSum = nums[0];
    for(let i=0;i<nums.length;i++){
        for(let j=i;j<nums.length;j++){
            if( j === i ){
                sum = nums[j]
            }else{
                sum += nums[j]
            } 
            if(sum >= maxSum){
                maxSum = sum
            }
        }
    }
    return maxSum
};

효성

첫 번째 시도 - `시간초과`


var maxSubArray = function(nums) {
    if(nums.length === 1) {
        return nums;
    }
    
    let sum = -Infinity;
    
    for(let i=0; i<nums.length; i++) {
        let compare = getMaxSum(nums.slice(i));
        if(sum < compare) {
            sum = compare;
        }       
    }
    return sum;
};

function getMaxSum(arr) {
    let maxSum = arr[0];
    let allSum = 0;
    
    for(let i=0; i<arr.length; i++) {
        allSum += arr[i];
        if(maxSum < allSum) {
            maxSum = allSum;
        }
    }
    return maxSum;
}

참고 답안


var maxSubArray = function(nums) {
  for (let i = 1; i < nums.length; i++) {
    nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
  }
  return Math.max(...nums)
};

현석


var maxSubArray = function(nums) {
    const dp = Array.from({length: nums.length}).fill(0)
    dp[0] = nums[0]
    
    for(let i = 0; i < nums.length - 1; i++) {
        dp[i + 1] = Math.max(dp[i] + nums[i + 1], nums[i + 1])
    }
    
    return Math.max(...dp)
};

Maximum Subarray

📄문제

✏️풀이

첫 번째 시도 - 시간초과

참고 답안

첫 번째 시도 - `시간초과`