릿코드 maximum subarray

2020-11-15

1. 릿코드 maximum-subarray

2. 문제

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.

2.1. 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.

2.2. Example 2:

Input: nums = [1]
Output: 1

2.3. Example 3:

Input: nums = [0]
Output: 0

2.4. Example 4:

Input: nums = [-1]
Output: -1
Example 5:

Input: nums = [-2147483647]
Output: -2147483647

Constraints:

1 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1

2.1. 컴퓨팅적 사고

값 나열시 하나의 규칙을 처음에 찾아보면서 dp를 사용하면 되겠다 생각하였습니다.

완전탐색

완전탐색의 경우 2중 포문을 사용하여 모든 경우 탐색하였는데 O(N)의 경우 시간초과

DP(dynamic programming)

DP의 경우 작은부분을 점차 늘려가면서 부분집합의 최댓값을 찾아주면 최종적으로 dp[length-1]에는 최적화된 값을 찾을 수 있습니다.(Bottom up)

2.2. 소스코드

public class leetcode_maximum_subarray_kgh {

    public static void main(String[] args) {
        maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4});
        maxSubArrayBruteforce(new int[]{-2,1,-3,4,-1,2,1,-5,4});
        maxSubArrayBruteforce(new int[]{-2147483647});
    }
    static int maxSubArray(int[] nums) {
        for(int i=1; i<nums.length; i++){
            nums[i] = Math.max(nums[i], nums[i]+ nums[i-1]);
        }
        Arrays.sort(nums);
        return nums[nums.length-1];
    }
    static int maxSubArrayBruteforce(int[] nums) {
        int max = -2147483647;      // 기존에 -1 넣었는데 입력이 -2147483647 예외 처리해주기 위해서 초기화
        for(int i=0; i<nums.length; i++){
            int sum = 0;
            for(int j=i; j<nums.length; j++){
                sum += nums[j];

                if(sum > max){
                    max = sum;
                }
            }
        }
        return max;
    }
}

Algorithmleetcode