Maximum no overlap window

 You are a programmer in a scientific team doing research into particles. As an experiment, you have measured the position of a single particle in N equally distributed moments of time. The measurement made in moment K is recorded in array A as A[K]. 
 Now, your job is to count all the periods of time when the movement of the particle was stable. Those are the periods during which the particle doesn't change its velocity: i.e. the difference between any two consecutive position measurements remains the same. Note that you need at least three measurements to be sure that the particle didn't change its velocity. 
 
  1,  3,  5,  7,  9  is stable (velocity is 2)
      7,  7,  7,  7  is stable (particle stays in place)
      3, -1, -5, -9  is stable (velocity is -4)
              0,  1  is not stable (you need at least three measurements)
  1,  1,  2,  5,  7  is not stable (velocity changes between measurements) 

More formally, your task is to find all the periods of time A[P], A[P+1], ..., A[Q] (of length at least 3) during which the movement of the particle is stable. Note that some periods of time might be contained in others (see example test).


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


that, given array A consisting of N integers representing the results of the measurements, returns the number of periods of time when the movement of the particle was stable. The function should return −1 if the result exceeds 1,000,000,000



Given array A = [−1, 1, 3, 3, 3, 2, 3, 2, 1, 0] the function should return 5, because there are five periods during which the movement of the particle is stable, namely: (0, 2), (2, 4), (6, 9), (6, 8) and (7, 9). Note that the last two periods are contained by (6, 9)

 

Assume that:

 

• N is an integer within the range [0..100];

• each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

Copyright 2009–2020 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

sdfsdf

https://github.com/luckypeak/practice/blob/2a1db208e397697247e7e0d88961934fc8368b5a/leetcode/src/main/java/MaxSumTwoNoOverlap.java

luckypeak/practice

Alice and Bob work in a beautiful orchard. There are N apple trees in the orchard. The apple trees are arranged in a row and they are numbered from 1 to N.

Alice is planning to collect all the apples from K consecutive trees and Bob is planning to collect all the apples from L consecutive trees. They want to choose two disjoint segments (one consisting of K trees for Alice and the other consisting of L trees for Bob) so as not to disturb each other. What is the maximum number of apples that they can collect?

Write a function:

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

that, given an array A consisting of N integers denoting the number of apples on each apple tree in the row, and integers K and L denoting, respectively, the number of trees that Alice and Bob can choose when collecting, returns the maximum number of apples that can be collected by them, or −1 if there are no such intervals.

For example, given A = [6, 1, 4, 6, 3, 2, 7, 4], K = 3, L = 2, your function should return 24, because Alice can choose trees 3 to 5 and collect 4 + 6 + 3 = 13 apples, and Bob can choose trees 7 to 8 and collect 7 + 4 = 11 apples. Thus, they will collect 13 + 11 = 24 apples in total, and that is the maximum number that can be achieved.

Given A = [10, 19, 15], K = 2, L = 2, your function should return −1, because it is not possible for Alice and Bob to choose two disjoint intervals.

Assume that:

• N is an integer within the range [2..600];

• K and L are integers within the range [1..N − 1];

• each element of array A is an integer within the range [1..500].

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

import java.io.IOException;
import java.util.Arrays;
//https://algorithms.tutorialhorizon.com/dynamic-programming-maximum-subarray-problem/

public class Solution {

	// Maximum Subarray Problem
	public static int solution(int[] A, int K, int L) {
		int len = A.length;
		if (len%2!=0) return -1;
		int[] arr = new int[len];
		arr[0] = A[0];

		for (int i = 1; i < len; i++) {
			arr[i] = arr[i-1] + A[i];
		}
		//System.out.println(Arrays.toString(arr));
		
		int alice = arr[K-1];
		int bob = arr[L-1];
		int total = arr[L+K-1];

		for (int i = L + K; i < len; i++) {
			alice = Math.max(alice, arr[i-L]-arr[i-L-K]);
			System.out.println(alice);
			bob = Math.max(bob, arr[i-K]-arr[i-K-L]);
			System.out.println(bob);
			int a = alice+arr[i]-arr[i-L];
			int b= bob+arr[i]-arr[i-K];
			total = Math.max(total, Math.max(a, b));
			System.out.println(total);
			
			System.out.println();
		}
		
		return total;

	}

	public static void main(String[] args) throws IOException {
		//int[] A = new int[] { 6, 1, 4, 6, 3, 2, 7, 4 };
		int[] A = new int[] { 10,19,15};
		//System.out.println(solution(A, 3, 2));
		System.out.println(solution(A, 2, 2));
	}

}