[백준, BOJ 1912] 연속합 (java)

출처-https://www.acmicpc.net/problem/1912

1912번: 연속합

---

728x90

---

내가 푼 방식 :

dp[i]에는 arr[i]가 저장되어 있다.
만약 dp[i-1]이 음수라면 dp[i]은 그대로 나두고,
dp[i-1]이 양수라면 dp[i]에 dp[i-1]을 더해준다.

 

==>>처음에 arr[i-1]가 음수면 합이 작아지게 한다고 생각하고 dp[i]에 dp[i-1]를 더하지 않고 그냥 dp[i]=arr[i] 해주었다.

이렇게 하면 음수인 arr[i-1]를 포함하더라도 연속배열을 늘려 dp[i-1]를 더하는 것이 합이 더 큰 경우가 생긴다. (예제 입력 2번)

그래서 dp[i-1]가 음수인 경우에만 더해주지 않고, dp[i]가 양수인 이상 포함하는 것이 합을 더 크게 만들 수 있다.

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner scan=new Scanner(System.in);
		int n=scan.nextInt();
		int arr[]=new int[n+1];
		long dp[]=new long[n+1];
		
		for (int i=1;i<=n;i++) {//n개의 정수 입력, arr,dp 배열 초기화
			arr[i]=scan.nextInt();
			dp[i]=arr[i];
		}
		
		for (int i=2;i<=n;i++) //연속된 수들이 가장 큰 합을 구하는 과정
			if (dp[i-1]>=0)
				dp[i]+=dp[i-1];
		
		long max=dp[1];
		for (int i=1;i<=n;i++) //가장 큰 dp 값 찾기
			if (max<dp[i])
				max=dp[i];
		System.out.println(max);
	}