LeetCode[day3] - 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.

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.

Example:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.

1. 알고리즘을 해결하기 위해서 생각한 방법

 Math.max와 변수 하나를 가지고, 어떻게 하면 되지 않을까라는 학습적인 생각이 머리에 떠올랐다. 하지만, 구체적인 생각은 떠오르지 않았고, 지금 값+ 다음 값, 지금 값 + 다음 값 + 다음 값, 이게 다다음값에 의해서 값이 바뀌지 않을까와 같은 생각이 머리를 혼잡하게 함.

 

2. 알고리즘 작성 중, 어려운 점

 - 그냥 잘 모르겠다.

 

3. 내가 작성한 알고리즘

 

//의미 없는 코드들

 

4. 다른 사람이 작성한 알고리즘 보기

 

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = nums[0];
        int result = nums[0];
        
        for(int i=1; i<nums.length; i++){
            sum = Math.max(nums[i] , nums[i]+sum);
            result = Math.max(sum, result);
        }
        return sum;
    }
}

 

5. 다른 사람이 작성한 알고리즘을 보고 배운점

 

 - 처음 코드를 봤을 때, 몇 줄 안되는 코드이지만, 머릿 속으로 잘 그려지지 않는다.

 그래서 메인 알고리즘 로직을 그려보면서, 접근해보니까 nums[i]와 nums[i]+sum을 통해서 이전에 작은 값이 나오게 되었을 때, nums[i]는 현재 값만 바라보게 하고, 이전 값이 큰 값이 나올 때는 nums[i]+sum을 통해서 누적해 나가는 것을 통해서 연속 된 숫자들의 누적 값을 구현한다는 것을 알게 되었다. 

 

6. 짝짝짝

 

내 코드는 아니지만, 참 대단하당.