LeetCode - 53. Maximum Subarray

 

 

Maximum Subarray - LeetCode

---

문제

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

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

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

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.

---

연속되는 subarray 중에서 가장 큰 합을 가지는 subarray를 찾아서 합을 리턴하라.

 

Brutal Force 로 푼 코드

class Solution {
    public int maxSubArray(int[] nums) {
        int answer = -2147483648;
        
        if (nums.length == 1){
            return nums[0];
        }
            
        for(int i = 0 ; i < nums.length ; i++){
            int temp = 0;
            for(int j = i ; j < nums.length ; j ++){
                // System.out.print("(" + nums[i] + "," + nums[j]+")");
                temp = temp + nums[j];
                if(answer < temp){
                    answer = temp;
                }
            }
            // System.out.println("sum = " + temp);
        }
        return answer;   
    }
}

 

Runtime: 122 ms, faster than 5.95% of Java online submissions for Maximum Subarray.

 

전체 subArray 경우의 수를 iterate 하기 때문에  많이 느리다.

 

최대합이 될 수 있는 조건을 생각 해 보자.

 

• -2 1 -3 4 -1 2 1 -5 4 에서 -2 음수로 시작하는 array는 최대합이 될 수 없다.
• -2 1 로 시작하는 subarray는 최대합이 될 수 없다.
• 결국 4에서 시작해야 한다. (뒤로 더하는 경우가 전부 합이 양수라서)

 

코드로 짜면

 

runningSum을 설정하고 음수가 될 때 runningSum을 0으로 설정한다.

ex)

array : [-2,1,-3,4,-1,2,1,-5,4,-10,100]

runSum : [0,1,0,4,3,5,6,1,5,0,100]

 

여기에 최대합이 음수일 때를 처리해주면

class Solution {
    public int maxSubArray(int[] nums) {
        int maxAnswer = 0;
        int answer = 0;
        int maxNumber = -2147483648;
        
        if(nums.length == 1){
            return nums[0];
        }
        
        
        for(int i = 0 ; i < nums.length ; i++){
            int num = nums[i];
            if(maxNumber < num){
                maxNumber = num;
            }
            if(answer + num < 0){
                answer = 0;
            }else{
                answer = answer + num;
                if(maxAnswer < answer){
                    maxAnswer = answer;
                }
            }
            // System.out.println(answer);
        }
        
        if(maxAnswer == 0){
            return maxNumber;
        }
        
        return maxAnswer;   
    }
}

 

Runtime: 1 ms, faster than 63.56% of Java online submissions for Maximum Subarray.

 

많이 빨라진걸 볼 수 있다.

 

 

 

[참고영상]