[SWEA] 3819 최대 부분 배열

출처: [SWEA] SW 문제해결 심화 - Ad Hoc Algorithms

 Input 

2

1

3

5

1

3

-5

3

6

 

 Output 

#1 3

#2 9

연속되는 부분 배열의 최대합을 구하는 문제

---

import java.util.Scanner;
 
public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        int T = Integer.parseInt(sc.next());
         
        for(int tc=1; tc<=T; tc++) {
             
            int N = Integer.parseInt(sc.next());
            int[] arr = new int[N];
            for(int i=0; i<N; i++) {
                arr[i] = Integer.parseInt(sc.next());
            }
             
            System.out.print("#" + tc + " ");
            System.out.println(findMaxSubArray(arr));
        }
    }
 
    private static int findMaxSubArray(int[] A) {
        int N = A.length;
        int answer = Integer.MIN_VALUE;
        int partialSum = 0;
         
        for(int i=0; i<N; i++) {
            partialSum = Math.max(partialSum, 0) + A[i];
            answer = Math.max(partialSum, answer);
        }
         
        return answer;
    }
}