[백준 13398, Java] 연속합2

문제

www.acmicpc.net/problem/13398

13398번: 연속합 2

처음풀이(시간초과)

- 삭제할 인덱스를 선택한다. for문을 돌면서 i까지 연속하는 최대합을 구하는데, i = index이면 이전의 합을 그대로 가져온다. 

- 이 경우 이중 for문으로 시간복잡도가 N제곱이 되면서 시간초과가 난다. 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[] numArray;
    public static int[] seqSums;
    public static int max;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        numArray = new int[N+1];
        seqSums = new int[N+1];


        st = new StringTokenizer(br.readLine()," ");
        for(int index = 1; index<= N; index++){
            numArray[index] = Integer.parseInt(st.nextToken());
        }

        getSeqSum();
        bw.write(String.valueOf(max));
        bw.flush();

        br.close();
        bw.close();

    }

    public static void getSeqSum(){
        for(int i = 0; i<=N; i++){
            int removeIndex = i;
            int removeValue = numArray[removeIndex];

            numArray[removeIndex] =0;
            for(int j = 1; j<=N; j++){
                if(j!=i){
                    seqSums[j] = Math.max(seqSums[j-1]+numArray[j],numArray[j]);
                    if(j ==1){
                        max = seqSums[j];
                    }
                    else{
                        max = Math.max(max, seqSums[j]);
                    }
                }
            }
            numArray[removeIndex] =removeValue;
        }
    }

}

 

강의 듣고 푼 풀이( 이해불가 )

- sumEnd[i] 를인덱스 i를 마지막으로 하는 연속합의 최대라고 정의하고, sumStart[i]를 인덱스 i를 시작으로 하는 연속합의 최대라고 정의한다

 

- 인덱스 i를 삭제하는 경우 sumEnd[i-1] + sumStart[i+1] 을 더하면 i-1, i+1이 연속할때 연속하는 수열의 최댓값을 구할 수 있다. 

 

- 여기서 이해가 안됐던 부분은, 예를들어 10 -4 3 1 5 6 -35 에서 1을 삭제한다고 하면 

 

위의 풀이처럼 9+11을 하는게 index 3을 삭제할 때의 최댓값이 된다. 그런데 

위의 경우는 index 3을 삭제했을 때의 위의 풀이로 하게되면 -6이지만 실제 최대값은 -1이다. 이게 이해가 가지 않았다. 

그러니까 나는 sum[i] = sumEnd[i-1] + sumStart[i+1] 를 i를 삭제할 때 전체 수열에서 연속하는 수열의 최댓값으로 이해했다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[] numArray;
    public static int[] sumLast;        // index를 마지막으로 하는 연속합
    public static int[] sumStart;       // index를 시작으로 하는 연속합
    public static int max;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine().trim());
        numArray = new int[N+1];
        sumLast = new int[N+2];
        sumStart = new int[N+2];

        st = new StringTokenizer(br.readLine()," ");
        for(int index =1; index<=N ; index++){
            numArray[index] = Integer.parseInt(st.nextToken());
        }

        //index를 마지막으로 하는 연속합 구하기
        for(int index = 1 ;index<=N; index++){
            sumLast[index] = Math.max(sumLast[index-1]+numArray[index], numArray[index]);
        }

        //index를 시작으로하는 연속합 구하기
        for(int index = N; index>=1; index--){
            sumStart[index] = Math.max(sumStart[index+1]+numArray[index], numArray[index]);
        }

        //아무것도 안지웠을 때의 최댓값
        for(int index = 1; index<=N; index++){
            if(index ==1)max = sumLast[1];
            else max = Math.max(max, sumLast[index]);
        }

        //index를 지웠을때의 최댓값
        for(int index = 2; index<N ; index++){
            max = Math.max(max, sumLast[index-1]+sumStart[index+1]);
        }

        bw.write(String.valueOf(max));
        bw.flush();

        br.close();
        bw.close();

    }
}

 

 

 

이차원 배열로 다시 풀기!