[LeetCode- Ch3. 배열] 3. 부분배열 최댓값 (+ DP)

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

Maximum Subarray - LeetCode

 

1. DFS 이용 : 타임리밋 발생

2. DP 이용 : 현재까지 가장 큰 값 저장하는 배열

-> dy[0] : 배열의 첫번째 값으로 초기화

-> 반복은 nums[1]부터 시작해, 이전 배열의 값을 더한 값과 현재 배열 값 중 Max값 선택

 

1. DFS 이용

class Solution {
    static int n, answer;
    static int[] arr;
    static boolean flag;
    public int maxSubArray(int[] nums) {
        //1. DFS 시도
        n= nums.length;
        arr=nums;
        answer=Integer.MIN_VALUE;
      
        for(int i=0;i<n;i++){
            flag =true;
            DFS(i,arr[i]);
        }
        
        return answer;
    }
    public void DFS(int L, int sum){  
        answer=Math.max(answer, sum);
        if(L==n){
            return;
        }
        else{
            if(flag){
                flag=false;
                DFS(L+1, sum);
            }else{
            DFS(L+1, sum+arr[L]);
            }
        }
    }
}

 

2. DP 이용

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

+)세련된 풀이

class Solution {
    public int maxSubArray(int[] nums) {
    		
	   //1.
		int curMax = nums[0];
		int allMax = nums[0];
		
		for(int i=1; i<nums.length; i++) {
			//System.out.println("nums["+i+"] "+nums[i]+" nums["+i+"] "+"+curMax: "+(nums[i]+curMax));
			
			curMax = Math.max(nums[i], nums[i]+curMax);
			allMax = Math.max(allMax, curMax);
			
			//System.out.println("curMax: "+curMax+" allMax: "+allMax);
			//System.out.println("  ");
		
		}
		return allMax;
	}
}

 

---

 

 

class Solution {
    public int maxSubArray(int[] nums) {
        //최소 하나의 숫자를 포함한 부분수열 최댓값
        int n=nums.length;
        int[] dp = new int[n+1];
        dp[0]=nums[0];
        int answer=dp[0];
        
        for(int i=1;i<n;i++){
            dp[i]=Math.max(nums[i], dp[i-1]+nums[i]);
            answer=Math.max(answer,dp[i]);
        }
        
        return answer;
    }
}

 

 

class Solution {
    public int maxSubArray(int[] nums) {
        int n=nums.length;
        //초기값 설정
        int curMax=nums[0];
        int allMax=nums[0];
        
        for(int i=1;i<n;i++){
            curMax=Math.max(nums[i], curMax+nums[i]);
            allMax=Math.max(curMax, allMax);
        }
        return allMax;
    }
}