[leetcode] 53. Maximum Subarray

문제링크

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

input & output

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

---

Approach #1

내 현재 위치에서 앞의 인덱스와의 합중 가장 큰 값을 배열에 저장한다.
이때 dp 배열 확인. dp[i-1]의 값은 내 현재위치 이전의 합중 가장 큰 값 or 자기 자신을 저장한 것이다. 
dp[i-1]+nums[i] 가 max이면 dp[i]를 갱신해주고, 더한게 max가 아니라면 dp[i]=nums[i]해준다.


0 - [0]
1 - [1], [0,1]
2 - [2], [1,2], [0,2]
3 - [3], [2,3], [1,3], [0,3]

 0 1  2 3  4 5 6  7 8
-2 1 -3 4 -1 2 1 -5 4

-2 1 -2 4  3 5 6  1 5  

Solution #1

// N: nums.length
// time: O(N)
// space: O(N)
var maxSubArray = function(nums) {
    //edge case
    if(nums.length===1) return nums[0];
    
    const dp=[nums[0]];
    let max = nums[0];
    for(let i=1; i<nums.length; i++){
        dp[i]=Math.max(dp[i-1]+nums[i], nums[i]);
        max = Math.max(max, dp[i]);
    }
    return max;
};

Time Complexity

O(N)

N: nums.length
N만큼 for문을 돌며 dp배열에 값을 추가하고, 리턴할 max값을 갱신하기 때문

Space Complexity

O(N)

nums의 길이만큼 dp배열이 생성되기 때문

---

Solution #1이 효율이 너무 안좋아서(메모리 5퍼,,^-^)
효율 좋은 다른 코드를 살짝 참고했는데 dp배열을 안쓰고 풀었더라...
위의 풀이에서 dp배열을 사용하지 않고 변수만 선언해서 푼 풀이가 아래와 같다.

---

Approach #2

[-2,1,-3,4,-1,2,1,-5,4]

      0 1  2 3 4 5 6 7 8 
curr -2 1 -2 4 3 5 6 1 5
max  -2 1  1 4 4 5 6 6 6

//base case
curr=nums[0]
max=nums[0]

현재 내 값(nums[i])와 이전의 값(curr)을 더한것과, 현재 내 값 중 더 큰것을 curr로 택한다.
택한 curr과 이전의 max를 비교해 max를 갱신해준다.

Solution #2

// N: nums.length
// time: O(N)
// space: O(1)
var maxSubArray = function(nums) {
  let curr = nums[0];
  let max = nums[0];
  
  for(let i=1; i<nums.length;i++){
      curr = Math.max(nums[i], nums[i]+curr);
      max = Math.max(curr,max);
  }
  return max;
};

Time Complexity

O(N)

N: nums.length
nums의 길이만큼 for문을 돌며 curr과 max를 갱신하기 때문.

Space Complexity

O(1)

curr과 max라는 변수만 선언했기 때문에 공간복잡도는 상수값.

---