maxsum RTE (nonzero return code)

  • tajano5
    tajano5

    import java.util.Scanner;

    public class Main {
    static Scanner sc = new Scanner(System.in);
    static int MIN =-100;

    static int N;
    static int[] res;
    static int tmpRes;
    
    
    public static void main(String[] args) throws Exception {
    
    
        int numTest= sc.nextInt();
        int count=0;
        res=new int[numTest];
    
        int[] A= new int[50];
    
        while (numTest-- > 0) {
            N=sc.nextInt();
            for (int i = 0; i < N; i++)
                    A[i] = sc.nextInt();
    
            tmpRes=fastMaxSum(A,0,N);
    
            res[count]=tmpRes;
            count++;
            for(int i=0; i<N; i++)
            {
                A[i]=0;
            }
            tmpRes=0;
        }       
        for (int r : res)
        {
            System.out.println(r);
        }
    
    
    }
    
    
    private static int fastMaxSum(int[] a, int lo, int hi) {
        if(lo==hi) return a[lo];
    
        int mid=(lo+hi)/2;
    
        int left=MIN, right=MIN, sum=0;
        for(int i=mid; i>=lo; --i)
        {
            sum+=a[i];
            left=max(left,sum);
        }
        sum=0;
        for(int j=mid+1; j<=hi; ++j)
        {
            sum +=a[j];
            right=max(right,sum);
        }
    
        int single=max(fastMaxSum(a, lo, mid),fastMaxSum(a, mid+1, hi));
    
        return max(left+right,single);
    }
    
    
    private static int max(int left, int sum) {
        if(left>sum)
        return left;
        else
            return sum;
    }

    }
    제가 이렇게 풀었습니다. 어디서 런타임오류가 나는지 도무지 모르겠습니다. 힌트라도 부탁드려요


    5년 전
5개의 댓글이 있습니다.
  • Namnamseo
    Namnamseo

    int[] A= new int[50]; 의 사이즈가 너무 작은 게 아닐런지요


    5년 전 link
  • tajano5
    tajano5

    처음에 1000으로 설정했습니다. 혹시 너무커서 런타임오류가 나는게 아닐까해서 줄이고줄이고 했는데 50에서도 런타임오류가 발생하네요;;;


    5년 전 link
  • Namnamseo
    Namnamseo

    문제 N 제한은 10^{5}=100000이네요.


    5년 전 link
  • tajano5
    tajano5

    100000로 해도 런타임오류가...


    5년 전 link
  • Namnamseo
    Namnamseo
    for(int j=mid+1; j<=hi; ++j)
    

    이부분이 어떻게 쓰이는지 살펴보세요.


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