MAXSUM 문제 시간초과가 뜹니다.. 어디가 문제 일까요?

  • woo_06
    woo_06

    연속된 숫자의 합이 가장 큰 수를 구하는 문제입니다.
    예를들어
    2 3 -2 1 이면 2+3으로 5가 정답이 되고
    3 -2 6 이면 3-2+6으로 7가 정답이 되는 문제입니다.

    제가 문제를 푼 방식은 양수가 연속되면 양수끼리 묶어주고
    음수가 연속되면 음수 끼리 묶어준 다음 ArrayList에 저장을 했습니다.
    1 2 3 4 -1 -2 -3 2 3 4 라는 case가 있으면
    10 -6 9 으로 ArrayList에 저장하는 방법으로요.
    그다음
    10
    10-6
    10-6+9
    -6
    -6+9
    9
    이런식으로 2중 for문을 돌면서 제일큰 수를 찾는 방법입니다.

    그런데 시간초과가 뜹니다
    for문을 너무 많이 돌아서 시간초과가 뜨는것같은데
    더 좋은 방법이 있을까요?
    힌트 좀 부탁드립니다.ㅠㅠ

    import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int cases = sc.nextInt();
        while(cases>0){
            int numbers = sc.nextInt();
            int sum=0;
            int inputNumber;

            ArrayList<Integer> arrayNumber = new ArrayList<>();
            while(numbers>0){
                inputNumber = sc.nextInt();
                if((inputNumber * sum)<0){
                    arrayNumber.add(sum);
                    sum = inputNumber;
                }else{
                    sum += inputNumber;     
                }
                numbers--;
                if(numbers==0)
                    arrayNumber.add(sum);
            }
            sum =0;
            int maxNumber = arrayNumber.get(0);
            for(int i=0;i<arrayNumber.size();i++){
                for(int j=i; j<arrayNumber.size();j++){
                    sum += arrayNumber.get(j);
                    if(sum > maxNumber)
                        maxNumber = sum;
                }
                sum=0;
            }
            System.out.println(maxNumber);
            cases--;
        }

    }

}

    8년 전
2개의 댓글이 있습니다.
  • codeonwort
    codeonwort

    이중 for문을 하나의 for문으로 줄일 수 있습니다.

    인접한 양수들과 음수들을 묶은 배열을 ary라 하고 sum = ary[0]으로 시작합니다. 그러면 무조건 짝수 번째 숫자들은 양수, 홀수 번째 숫자들은 음수인데, 음수는 더해봤자이므로 항상 음수와 그 다음 양수를 같이 더해줍니다. 이 값이 음수면 다음 양수에서 새로 시작하고, 아니면 최대값을 갱신하는 식으로 시간복잡도를 O(n)으로 줄일 수 있습니다.

    max = sum = ary[0]
    for(i=1; i<n; i++){
      if(sum + ary[i] < 0) sum = ary[i+1]
      else sum += ary[i] + ary[i+1]
      if(sum > max) max = sum
    }


    8년 전 link
  • woo_06
    woo_06

    감사합니다. 잘 이해했습니다! 참고해보겠습니다 ㅎㅎ


    8년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.