Java program:Time coplextiy-O(n) ,Space Complexity-O(1)


#1

ArrayList array=new ArrayList();
int f_si=-1;
int f_ei=-1;
int c_si=0;
long c_max=0;
long f_max=Integer.MIN_VALUE;
for(int i=0;i<A.size();i++){
if(A.get(i)<0){
if(f_max<c_max){
f_max=c_max;
f_si=c_si;
f_ei=i-1;
c_max=0;
c_si=i+1;
}
else{
c_max=0;
c_si=i+1;
}
}
else{
c_max+=A.get(i);
}
}
if(f_max<c_max){
f_max=c_max;
f_si=c_si;
f_ei=A.size()-1;
}
for(int i=f_si;i<=f_ei;i++){
array.add(A.get(i));
}
return array;