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);
}
}