53. Maximum Subarray

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

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

O(N) 코드

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

Divide and Conquer

2ms

• ide 사용하고 debugging하는데 시간이 오래 걸림
• 2개또는 1개로 자른다.
• 데이터를 머지할때 3가지 데이터를 구한다
  • leftMost = 왼쪽 0번째 인덱스 부터 시작해서 가장 큰 sum을 구한다.
  • rightMost = 오른쪽 0번째 인덱스부터 왼쪽으로 가장 큰 sum을 구한다.
  • full 은 머지한전체 sum, leftMost와 rightMost를 구하기 위해서 필요함.

public class Solution {

    int max =0;
    int[] nums ;
    public int maxSubArray(int[] nums) {
        max = nums[0];
        this.nums = nums;
        divideAndConquer(0, nums.length-1);

        return max;
    }

    public Data divideAndConquer(int start, int end){
        Data data = new Data();
        if(start == end){
            data.full = nums[start];
            data.leftMost = nums[start];
            data.rightMost = nums[start];
            max = Math.max(max ,data.full);
            return data;
        }else if (start == end-1){
            data.full = nums[start] + nums[end];
            data.leftMost = Math.max(nums[start], nums[start] + nums[end]);
            data.rightMost = Math.max(nums[end], nums[start] + nums[end]);
            max = Math.max(max ,data.leftMost);
            max = Math.max(max ,data.rightMost);
            return data;
        }
        int mid = (end-start)/2 + start;
        // left
        Data left = divideAndConquer(start, mid);

        // right
        Data right = divideAndConquer(mid+1 ,end);
            
        if(left.rightMost >0 || right.leftMost >0){
            max = Math.max((Math.max(left.rightMost, 0) + Math.max(right.leftMost, 0)), max);
        }
        
        data.leftMost = Math.max(left.leftMost, left.full + right.leftMost);
        data.rightMost = Math.max(right.rightMost, right.full + left.rightMost);
        data.full = right.full + left.full;
        max = Math.max(max, data.leftMost);
        max = Math.max(max, data.rightMost);
        max = Math.max(max, data.full);
        return data;
    }

  
}

class Data {
    int leftMost;
    int full;
    int rightMost;
}