maxdoubleslicesum

A non-empty zero-indexed array A consisting of N integers is given.
A triplet (X, Y, Z), such that 0 ≤ X < Y < Z < N, is called a double slice.
The sum of double slice (X, Y, Z) is the total of A[X + 1] + A[X + 2] + … + A[Y − 1] + A[Y + 1] + A[Y + 2] + … + A[Z − 1].

The goal is to find the maximal sum of any double slice.

Solution:

class  {
    public int solution(int[] A) {
        
        int size = A.length;
        int[] sum1 = new int[size-2];
        int[] sum2 = new int[size-2];
        
        int max_end1 = 0, max_end2 = 0;//ignore A[0] and A[size-1]
        for(int i=1;i<size-2;i++){
            sum1[i] = Math.max(0, sum1[i-1]+A[i]);
            sum2[size-i-3] = Math.max(0, sum2[size-i-2]+A[size-i-1]);
        }
        int max = 0, sum;
        for(int j=0;j<size-2;j++){
            sum = sum1[j]+sum2[j];
            if(sum > max)
                max = sum;
        }
        return max;
    }
}

maxdoubleslicesum

近期文章

近期评论

标签

热门

文章归档

分类目录

功能