this solution finding out maximum sum of subarray given array using segment tree (http://www.spoj.com/problems/gss1/) getting tle (time limit exceeded error) this. can suggest more optimizations code?
public class segmenttree { int st[]; segmenttree(int arr[], int n){ int x = (int)math.ceil(math.log(n)/math.log(2)); int maxsize = (int)math.pow(2, x)<<1 - 1; st = new int[maxsize]; constructstutil(arr, 0, n-1, 0); } int getmid(int s, int e) { return s + (e - s)>>1; } int getsumutil(int ss, int se, int qs, int qe, int si) { if (qs <= ss && qe >= se) return st[si]; if (se < qs || ss > qe) return 0; int mid = getmid(ss, se); return getsumutil(ss, mid, qs, qe, si<<1 + 1) + getsumutil(mid + 1, se, qs, qe, si<<1 + 2); } int getsum(int n, int qs, int qe) { if (qs < 0 || qe > n - 1 || qs > qe) { return -1; } return getsumutil(0, n - 1, qs, qe, 0); } int constructstutil(int arr[], int ss, int se, int si) { if (ss == se) { st[si] = arr[ss]; return arr[ss]; } int mid = getmid(ss, se); st[si] = constructstutil(arr, ss, mid, si<<1 + 1) + constructstutil(arr, mid + 1, se, si<<1 + 2); return st[si]; } public static void main(string[] args) throws ioexception { bufferedreader in = new bufferedreader(new inputstreamreader(system.in)); int n = integer.parseint(in.readline().trim()); int array[] = new int[n]; string arr[] = new string[n]; arr = in.readline().split(" "); for(int i=0; i<n; i++){ array[i] = integer.parseint(arr[i].trim()); } segmenttree tree = new segmenttree(array, n); int m = integer.parseint(in.readline()); while(m-- > 0){ string ind[] = new string[2]; ind = in.readline().split(" "); int x = integer.parseint(ind[0].trim()); int y =integer.parseint(ind[1].trim()); int maxsum = -999999999; for(int i=x-1; i<=y-1; i++){ for(int j=x-1; j<=y-1; j++){ if(tree.getsum(n, i, j) > maxsum) maxsum = tree.getsum(n, i, j); } } system.out.println(maxsum); } } }
Comments
Post a Comment