문제

연속합

풀이

연속된 숫자를 더해서 나온 숫자중 가장 큰 수를 구하는 문제이다. 왜이렇게 기시감이 드는 문제인지. 정답률이 낮던데 다행히도 1솔만에 풀었따

dp배열에 들어갈 값으로는 현재 인덱스를 포함하여 연속으로 더했을때 가장 큰 값이 들어가면 된다.
값이 1 2 3이면
첫번째 배열에는 1
두번째 배열에는 3
세번째 배열에는 6

로직은 다음과 같다

int[] dp = new int[n];
dp[0] = arr[0]; // 가장 처을 배열이 dp[0] 값이 된다
int answer = arr[0]; // 가장 처음 배열을 초기 값을 넣어준다 
for (int i = 0; i < n; i++) {
	// 현재의 배열을 넣을 경우 : 현재 값보다 더 작은 경우
    // 이전의 배열의 값과 합한 값을 넣는 경우 : 연속합
	dp[i] = Math.max(arr[i] + dp[i - 1], arr[i]);
	answer = Math.max(answer, dp[i]);
}

전체 코드

전체 코드