leet code 53. Maximum Subarray

 

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.

 

 

정수가 들어있는 배열 하나가 주어진다.

배열안에 들어있는 정수들 중에서 숫자들의 하위배열이 가장 큰 배열의 합을 리턴하는 문제이다.

 

 

풀이법

 

 

class Solution {
    public int maxSubArray(int[] nums) {
    	
    	int n = nums.length;
    	int dp ;
    	
    	dp = nums[0];
    	
    	int max = dp;
    	
    	
    	for(int i =1 ; i < n; i++) {
    		dp = nums[i] +(dp > 0  ? dp : 0); 
    		max = Math.max(max, dp);
    	}
    	
    	
        
    	
    	return max;
    }
}

 

dp 라는 수는 전 하위배열의 합을 저장해주는 변수이다.

dp변수에 하위 배열의 합을 저장해 두었다가 전 배열의 합이 양수이면 더하고 음수이면

전 배열의 값의 합보다 작아지기때문에 dp 를 0으로 계산하여 현재의 수를 dp에 새롭게 저장한다.

큰값을 max 변수에 저장한뒤 비교한다.