Sunday, April 26, 2015

Maximum slice problem - MaxDoubleSliceSum

Here is another codility problem solution from the codility lessons (MaxDoubleSliceSum -Find the maximal sum of any double slice.) due to the copy rights I can't copy the content of the problem here so to view the problem description click here.




// you can also use imports, for example:
import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
	public int solution(int[] A) {
		int[] fromLiftDoubleSlices = new int[A.length];
		int[] fromRightDoubleSlices = new int[A.length];
		int max_ending = 0;
		for (int i = 1; i < A.length - 1; i++) {
			max_ending = Math.max(0, max_ending + A[i]);
			fromLiftDoubleSlices[i] = max_ending;
		}
		max_ending = 0;
		for (int i = A.length - 2; i > 0; i--) {
			max_ending = Math.max(0, max_ending + A[i]);
			fromRightDoubleSlices[i] = max_ending;
		}
		int maxSum = 0;
		for (int i = 1; i < A.length - 1; i++) {
			maxSum = Math.max(maxSum, fromLiftDoubleSlices[i - 1] + fromRightDoubleSlices[i + 1]);
		}



		return maxSum;
	}
}

No comments:

Post a Comment