I tried to optimize and now it looks like O(n) solution to me. Still TLE
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <memory.h>
using namespace std;
#define NMAX 100000
int A[NMAX+2];
int MAXI[NMAX+2] = {0};
int P[NMAX+2];
bool C[NMAX+2] = {0};
int IDX[NMAX+2];
int Print(int idx) {
if(idx==-1)
return 1;
return C[idx]+Print(P[idx]);
}
int main() {
int t, N,M,x,y;
scanf("%d",&t);
while(t--) {
scanf("%d",&N); int idxi=0;
for(int i=1;i<=N;i++) {
scanf("%d",&A[i]);
}
memset(C,0,sizeof C);
int maxi = A[1]; int idx = 1;IDX[0] = 1;int pred = 1;
for(int i=1;i<=N;i++){
if(A[i] <= MAXI[i-1]+A[i]) {
if((i-1)>0 && MAXI[i-1]==0)
C[i] = 1;
MAXI[i] = MAXI[i-1]+A[i];
P[i] = i-1;
}
else {
MAXI[i] = A[i];
P[i] = -1;
}
if((maxi == MAXI[i])) {
IDX[idxi++] = i;
}
if((maxi < MAXI[i])) {
idxi = 1;
maxi = MAXI[i];
IDX[0] = i;
}
}
P[1] = -1;
int cnt = 0;
for(int i=0;i<idxi;i++) {
cnt+=Print(IDX[i]);
}
printf("%d %d\n",maxi,cnt);
}
return 0;
}