[LeetCode-53] Maximum Subarray 문제풀이 - Java 사용

Maximum Subarray 문제풀이 - Java 사용

구글번역을 이용하여 번역

요약 : 정수배열이 있고 연속되는 부분 배열중에서 합이 가장 큰것을 리턴하라

 

방법1 -> for문 2개 사용 

첫 번째 for문은 입력받은 값(매개변수)에 대해 길이만큼 돌면서 max값을 임시변수(tmp)에 저장하는 것

두 번째 for문은 tmp에 저장된 배열을 비교하면서 max값을 찾아 리턴

//[-2,1,-3,4,-1,2,1,-5,4]
class Solution {
  public int maxSubArray(int[] nums) {      
        
        int [] tmp = new int[nums.length];
        tmp[0] = nums[0];        
        
        for(int i = 1; i<nums.length; i++){
            // num : -2 1            
            // tmp : -2 Max(-1,1) -2+1 or 아님 나자신 
            // tmp[i] : i번째 값이 마지막 원소인 부분배열의 합 중 최댓값
            // tmp[3] : max(nums[2], nums[1]+nums[2], nums[0]+nums[1]+nums[2])
            tmp[i] = Math.max(tmp[i-1], nums[i]);           
        }        
        // tmp 첫번째 값 -2
        int max = tmp[0];
        // tmp -2, 1, 1, 4, 4, 4, 4, 4, 4
        for(int num : tmp){
            if(num > max){
              max = num;  
            } 
        }            
           return max;        
    }
}

방법 2 -> 삼항 연산자이용

방법 1에비해 시간복잡도가 줄어듦

// 정수배열이 있고 연속되는 부분 배열중에서 합이 가장 큰거 리턴
class Solution {
   public static int maxSubArray(int[] nums) {
       
       
       // 초기값 -2 
        int Max = nums[0];
       // 초기값 -2
        int prev = nums[0];
       
       // for문을 이용하여, 값을 비교하고
       // Max와 prev의 값을 비교해서 최 댓값 구하기
        for(int i = 1; i < nums.length; i++) {
            // 1 > 1 + -2 = ? 1 : -1 -> 1
            prev = nums[i] > nums[i] + prev ? nums[i] : nums[i] + prev;
            // -2 > 1 ? -2 : 1 -> 1
            Max = Max > prev? Max: prev;            
        }
        return Max;
    }         
}