Codility_MaxSliceSum

9-2. MaxSliceSum

A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers, returns the maximum sum of any slice of A.

For example, given array A such that:

A[0] = 3 A[1] = 2 A[2] = -6
A[3] = 4 A[4] = 0
the function should return 5 because:

(3, 4) is a slice of A that has sum 4,
(2, 2) is a slice of A that has sum −6,
(0, 1) is a slice of A that has sum 5,
no other slice of A has sum greater than (0, 1).
Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..1,000,000];
each element of array A is an integer within the range [−1,000,000..1,000,000];
the result will be an integer within the range [−2,147,483,648..2,147,483,647].

비어 있지 않은 N개의 정수로 구성된 배열 A가 주어집니다. 0 ≤ P ≤ Q < N인 두 정수 (P, Q) 쌍을 배열 A의 슬라이스라고 합니다. 슬라이스 (P, Q)의 합은 A[P] + A[P+1] + … + A[Q]의 총합입니다.

다음과 같은 함수를 작성하세요:

class Solution { 
    public int solution(int[] A); 
}

이 함수는 N개의 정수로 구성된 배열 A가 주어졌을 때, 배열 A의 모든 슬라이스 중 최대 합을 반환해야 합니다.

예를 들어, 배열 A가 다음과 같다면:

A[0] = 3 A[1] = 2 A[2] = -6 A[3] = 4 A[4] = 0

함수는 5를 반환해야 합니다. 그 이유는:

(3, 4)는 합이 4인 슬라이스입니다.
(2, 2)는 합이 -6인 슬라이스입니다.
(0, 1)는 합이 5인 슬라이스입니다.
다른 어떤 슬라이스도 (0, 1)보다 큰 합을 가지지 않습니다.
다음 가정을 만족하는 효율적인 알고리즘을 작성하세요:

N은 [1…1,000,000] 범위 내의 정수입니다.
배열 A의 각 요소는 [-1,000,000…1,000,000] 범위 내의 정수입니다.
결과는 [-2,147,483,648…2,147,483,647] 범위 내의 정수입니다.

문제풀이

import java.util.*;

class Solution {
    public int solution(int[] A) {
        int BigListCheck = A[0];
        int BigList = A[0];
        for(int i = 1; i < A.length; i++){
            BigListCheck = Math.max(A[i], BigListCheck + A[i]);
            BigList = Math.max(BigList, BigListCheck);
        }
        return BigList;
    }
}

Math.max()를 사용하여
A배열을 이전 반복문만큼 더한 것(BigListCheck)과
현재 반복회차의 새로운 A배열의 값이 큰지 체크해고 둘중 큰 값을 BigListCheck의 값에 넣습니다.
A[0]=1, A[1]=1, A[2]=3 일 경우
2번째 반복시에 BigListCheck는
3("A[2]") 즉 "3"
1(BigListCheck의 초기값) + 1(A[1]) 즉 "2"를 비교하여 큰값 A[2]를 BigListCheck로 업데이트합니다,
그다음 BigListCheck와 최종 BigList를 비교하여 최종값을 업데이트합니다.

제출결과

문제풀어보기 -> https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_slice_sum/