NKMAXSEQ - Dãy con dài nhất

Tác giả: khuc_tuan

Ngôn ngữ: Java

import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.*;

import com.sun.corba.se.spi.orbutil.fsm.Input;

public class Main {
	
	public static void main(String[] args) throws Exception {
		BufferedReader kb = new BufferedReader( new InputStreamReader(System.in));
		Scanner sc = new Scanner(kb.readLine());
		int n = sc.nextInt();
		int P = sc.nextInt();
		int[] imin = new int[n+1];
		int[] a = new int[n+1];
		for(int i=1;i<=n;++i) a[i] = a[i-1] + Integer.parseInt(kb.readLine());
		imin[0] = 0;
		for(int i=1;i<=n;++i) 
			if(a[i]<a[imin[i-1]]) imin[i] = i;
			else imin[i] = imin[i-1];
		int rj = n;
		int result = -1;
		for(int i=n-1;i>=0;--i) if(imin[i]==i) {
			int j;
			for(j=rj;j>i;--j) if(a[j]-a[i]>=P) {
				result = Math.max( result, j-i);
				break;
			}
			rj = j;
		}
		System.out.println(result);
	}
}

Download