[Medium] 53. Maximum Subarray

Leetcode 53번 문제는 주어진 array에서 주어진 값을 더했을때 가장 합이 큰 subarray를 찾는 문제이다. 

#Brute Force 풀이

class Solution {
    public int maxSubArray(int[] nums) {
        int  max = nums[0];
 
        for(int i=0; i<nums.length;i++){
                       int sum = 0;
            for(int j=i; j<nums.length;j++){
               sum += nums[j];
               max = Math.max(max, sum); //if(sum >= max){max = sum;} 와 같음
            }
        }
        return max;
    }
}

#Kadane's Algorithm (카데인 알고리즘) 풀이

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

#Sliding Window Technique 풀이

class Solution {
    public int maxSubArray(int[] nums) {
        int i = 0, j = 1;
        int sum = 0, max = Integer.MIN_VALUE;
        
        while(j <= nums.length){
            sum += nums[j-1];
            max = Math.max(sum, max);
            
            if(sum <= 0){
                i = j;
                sum = 0;
            }
            
            j++;
        }
        
        return max;
    }
}