Codility : MaxSliceSum 풀이 Java, DP

문제

MaxSliceSum coding task - Learn to Code - Codility

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].

 

 

풀이

 

Maximum Subarray(최대 부분 합 구하기) 문제는 Kadane’s Algorithm을 활용한 대표적인 문제이다.

 

pdf 9.3 참고

https://codility.com/media/train/7-MaxSlice.pdf

 

1차원 배열을 사용해서 문제를 풀어도 되지만

여기서 사용되는 공식은 아래와 같기 때문에 1차원 배열에 저장할 필요 없이 바로 앞의 최댓값만 저장하면 된다.(slicing)

Max(자기자신, 바로 앞의 최대 + 자기자신)

 

Slicing에 저장되는 값은 앞에서부터 값을 더해온다고 했을 때, 시작을 어느 위치에서 했든 그 위치에서 얻을 수 있는 가장 큰 값이다.

 

A={3, 2, -6, 4, 0} 일 때 Slicing, Max 값

Index	0	1	2	3	4
Slicing	3	5	-1	4	4
Max	3	5	5	5	5

 

 

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

		int slicing = A[0];
		int max = A[0];

		for (int i = 1; i < A.length; i++) {
			int v = A[i];
			slicing = Math.max(slicing + v, v);
			max = Math.max(max, slicing);
		}
		return max;
	}
}

 

 

카데인 알고리즘 참고하면 좋은 블로그

https://byeong9935.tistory.com/105

Kadane’s Algorithm (카데인 알고리즘)