[Algorithm/Java][LeetCode] 53. Maximum subarray

[LeetCode] 53. Maximum subarray

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

문제접근

주어진 배열에서 연속되는 값을 더한 sum이 가장 큰 subarray의 sum을 찾는 문제이다.
처음에 이 문제를 보자마자 다이나믹 프로그래밍인 것 같아서 dp라는 배열을 만들고 dp[i]는 i번째 인덱스까지 중에 가능한 가장 큰 subarray의 값을 저장하는 배열로 만들어서 풀었다.(방법1)
근데 방법1로 풀고보니까 굳이 dp라는 배열을 만들어서 일일이 다 저장할 필요 없이 현재인덱스 전의 subarray값(dp[i-1])만 알면 될 거 같았다. 즉 배열을 만들지 않고 dp[i-1]을 저장하는 sum이라는 변수를 만들어서 dp[i-1] 이전 값(dp[i-2] ... dp[0])의 값은 저장하지 않고 푸는 방식을 썼다.(방법2)
하지만 이상하게도 LeetCode에서 제공해주는 Runtime과 Memory 값에서는 방법 1의 메모리가 더 적었다.(????) (아래가 방법1, 위가 방법2)

Code

//방법1
class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = nums; // dp = 해당 인덱스에서 가장 큰 값을 저장하는 배열
        dp[0] = nums[0];
        int max = dp[0]; // sum의 최댓값 저장
        for(int i = 1; i<nums.length; i++){
            if(dp[i] < dp[i-1] + nums[i]){
                // 현재 값보다 i-1번째 최대값 + 현재 인덱스 값이 클 경우
                dp[i] = dp[i-1] + nums[i];
            }
            if(max < dp[i])
                    max = dp[i];
        }
        return max;
    }
}

//방법2
class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0]; // 최대값 저장
        int sum = nums[0]; // 지금까지 sum 값
        for(int i = 1; i<nums.length; i++){
            sum = Math.max(sum+nums[i] , nums[i]); //sum + 현재값 과 현재값 중 큰것을 sum에 저장
            max = Math.max(sum,max); // sum이 큰 지 max가 큰 지 비교
        }
        return max;
    }
}

어려웠던 점 / 배운 점 / 느낀 점

뭔가 느낌이 다이나믹 프로그래밍이여서 풀었는데 맞는듯 싶다.(?)
방법 2가 방법 1 보다 실행시간은 몰라도 메모리는 더 효율적일 줄 알았는데 아니여서 충격적이였다.
내가 세운 가설은

• sum에 새로운 값을 넣을 때 메모리가 증가하나?
• Math.max 가 문제인가?
  그래서 삼항연산자로 코드를 바꿔보았다.

  //방법3
  class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0]; // 최대값 저장
        int sum = nums[0]; // 지금까지 sum 값
        for(int i = 1; i<nums.length; i++){
            sum = Math.max(sum+nums[i] , nums[i]); //sum + 현재값 과 현재값 중 큰것을 sum에 저장
            max = Math.max(sum,max); // sum이 큰 지 max가 큰 지 비교
        }
        return max;
    }
  }

  결론은 Math.max가 문제였던 것 같다! 👍👍
  

  

앞으로 Math.max 보다는 삼항 연산자를 사용해야겠다..!!