[다이나믹]-1912_연속합

admin1194·2021년 2월 2일
0

알고리즘문제풀이

목록 보기
13/45

링크텍스트

배열이 주어졌을 때 연속적(인접한 인덱스끼리)으로 더했을 경우 가장 큰 값을 골라내야 하는 로직을 짜는 문제였다.

예제
10 -4 3 1 5 6 -35 12 21 -1

연속적으로 옆에 있는 수를 더함으로써 최댓값인지 아닌지를 판별하는 문제로 인접한 수가 더하는데 연관이 있으므로 다이나믹으로 풀 수 있는 문제인 것 같았다.
문제를 작게 만들어서 ..? 문제를 작게 만들면 배열의 범위를 작게 만들어서 차근차근 해결하는 것이 포인트이다.

i=1부터 루프문을 수행하여.
10을 dp[0]에 저장을 해두고
dp[1] 에서 이제 지금 -4 자체가 큰지 혹은 10을 더하는 것이 큰 지 비교를 하는것이다
dp[1]에는 10-4 > -4 보다 크므로 dp[1]=6이 들어가게 되고
i==2에서
dp[2]=이전 계산된 d[1]하고 현재 3을 더한값이 그냥 있는 3보다 큰가 비교를 하고 덯는다..

이렇게 쭈욱 더함으로써
dp[]에는 최댓값이 계속 저장되 있는 것이 아니라 이 원소안에는 음수 또한 존재한다. 이제 해당 dp에 음수가 저장되면 아까 계속 필터링 해왔던 것을 여기에서도 적용하여서 dp에 저장되있던 음수를 현재 수를 더한 값과 지금 현재 값 중에 무엇이 큰지를 비교한다. 이과정에서 dp에 음수값이 들어있고 현재 배열의 원소가 양수이면 그로부터 지금까지 더해왔던 적업의 dp는 -가아닌 그 해당 양숭인 인덱스 기준으로 값이 변화하면서 계속해서 더해가면서 수를 만들고 지금까지 더했던 값중에 가장 큰 수를 추출하기 위해 오름차순으로 정렬을 해준 후 마지막 인덱스에 있는 원소를 출력하면 해결할 수 있다.

해당 dp는 해당 인덱스 자리에있는 수 까지 비교하였을 때 누적으로 가장 큰 값이 dp에 저장된다는 것을 알 수 있다.

package Thur_Sunday_aWeek_Al.Random;

import java.util.Arrays;
import java.util.Scanner;

public class sequenceSum {
   public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       int n=sc.nextInt();

       int arr[]=new int[n];
       for (int i = 0; i < n; i++) {
           arr[i]=sc.nextInt();
       }
       int dp[]=new int[n];
       dp[0]=arr[0];

       for (int i = 1; i < n; i++) {
           dp[i]=Math.max(dp[i-1]+arr[i],arr[i]);
       }

       Arrays.sort(dp);
       System.out.println(dp[n-1]);
   }
}
//https://zoonvivor.tistory.com/152
profile
Record then ㄱ

0개의 댓글