Re: [algogeeks] Re: matrix
@sinjanspecial: i think your code is for an 1 D matrix..but i have to find for a 2D matrix.. On Sat, Sep 17, 2011 at 7:33 PM, sinjanspecial sinjanspec...@gmail.comwrote: hii I think this code will work #includestdio.h #includestring.h void largestsum(int a[],int n) { int s=0,e=0,ls=0,max=0,j,i,sum=0; for(i=0;in;i++) { sum+=a[i]; if(summax) { max=sum; e=i; s=ls; } if(sum0) { sum=0; ls=i+1; } } printf(\nlargest sum is=%d\n,max); printf(The element which make largest sum is\t); for(j=s;j=e;j++) { printf(%d\t,a[j]); } } int main() { int a[]={6,4,-5,5,2,8,-21,15,4}; int n=9; largestsum(a,n); return 0; } Thanks Regards Sinjan M.Tech(s/w engg) DTU delhi On Sep 17, 2:55 pm, prasanth n nprasnt...@gmail.com wrote: given a matrix with +ve and -ve numbers, find the submatrix with maximum sum?? -- *prasanth* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *prasanth* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: matrix
people just dont read the question properly and post the answer On 9/17/11, prasanth n nprasnt...@gmail.com wrote: @sinjanspecial: i think your code is for an 1 D matrix..but i have to find for a 2D matrix.. On Sat, Sep 17, 2011 at 7:33 PM, sinjanspecial sinjanspec...@gmail.comwrote: hii I think this code will work #includestdio.h #includestring.h void largestsum(int a[],int n) { int s=0,e=0,ls=0,max=0,j,i,sum=0; for(i=0;in;i++) { sum+=a[i]; if(summax) { max=sum; e=i; s=ls; } if(sum0) { sum=0; ls=i+1; } } printf(\nlargest sum is=%d\n,max); printf(The element which make largest sum is\t); for(j=s;j=e;j++) { printf(%d\t,a[j]); } } int main() { int a[]={6,4,-5,5,2,8,-21,15,4}; int n=9; largestsum(a,n); return 0; } Thanks Regards Sinjan M.Tech(s/w engg) DTU delhi On Sep 17, 2:55 pm, prasanth n nprasnt...@gmail.com wrote: given a matrix with +ve and -ve numbers, find the submatrix with maximum sum?? -- *prasanth* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *prasanth* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- * Regards* *The Coder* *Life is a Game. The more u play, the more u win, the more u win , the more successfully u play* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: matrix
@prasanth : sinjalspecial is correct bt his code works for 1D array . for 2D array you can think of array of 1D array and then implement the same . newazz here is one link : http://tech-queries.blogspot.com/2010/05/find-max-sum-in-2d-array.html On Sat, Sep 17, 2011 at 8:43 PM, tech coder techcoderonw...@gmail.comwrote: people just dont read the question properly and post the answer On 9/17/11, prasanth n nprasnt...@gmail.com wrote: @sinjanspecial: i think your code is for an 1 D matrix..but i have to find for a 2D matrix.. On Sat, Sep 17, 2011 at 7:33 PM, sinjanspecial sinjanspec...@gmail.comwrote: hii I think this code will work #includestdio.h #includestring.h void largestsum(int a[],int n) { int s=0,e=0,ls=0,max=0,j,i,sum=0; for(i=0;in;i++) { sum+=a[i]; if(summax) { max=sum; e=i; s=ls; } if(sum0) { sum=0; ls=i+1; } } printf(\nlargest sum is=%d\n,max); printf(The element which make largest sum is\t); for(j=s;j=e;j++) { printf(%d\t,a[j]); } } int main() { int a[]={6,4,-5,5,2,8,-21,15,4}; int n=9; largestsum(a,n); return 0; } Thanks Regards Sinjan M.Tech(s/w engg) DTU delhi On Sep 17, 2:55 pm, prasanth n nprasnt...@gmail.com wrote: given a matrix with +ve and -ve numbers, find the submatrix with maximum sum?? -- *prasanth* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *prasanth* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- * Regards* *The Coder* *Life is a Game. The more u play, the more u win, the more u win , the more successfully u play* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: matrix finding immediate neighour
@ shashank and all can we an approach that take less time than O(N^2). I mean not in O(N ) or nlogn but n^2 some optimiation On Thu, Aug 25, 2011 at 8:43 PM, WgpShashan) k shashank7andr...@gmail.com wrote: @Sharvan ..Yes We Can do That and yes i forgot that intead of locals.add(a[i][j]) , we need tow write locals.add(i+j) Hope its fine now :) *Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/FKYupw3YSG4J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: matrix finding immediate neighour
@Shashank You can enhance further by moving border condition check for i j before you access them i.e, (i0 j0 ) ( lm a[i-1][j-1] ) ; also location is to be saved not numbers. :) On Thu, Aug 25, 2011 at 5:35 PM, WgpShashank shashank7andr...@gmail.comwrote: If i got the question correct then its Simple Straightforward, We need to Check All neighbors, With Boundary conditions public static ListInteger findLocalMaxima(Integer a[][]) { ListInteger locals = new ArrayListInteger(); int row=a.length; for (int i = 0; i row;i++) { int col=a[i].length; for (int j = 0; j col; j++) { Integer lm=a[i][j]; Boolean aa= ( lm a[i-1][j-1] ) (i0 j0 ); Boolean b=(lm a[i][j-1]) j0; Boolean c= (lm a[i-1][j]) i0; Boolean d= (lm a[i][j+1]) jcol-1; Boolean e= (lm a[i-1][j+1]) (i0 jcol-1); Boolean f= (lm a[i+1][j-1]) (irow-1 j0); Boolean g= (lm a[i+1][j]) irow-1; Boolean h= (lm a[i+1][j+1]) (irow-1 jcol-1); if( aa b c d e f g h ) locals.add(a[i][j]); } } return locals; } correct me if anything wrong ? *Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/5xmX_nyPRKkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: matrix finding immediate neighour
@Sharvan ..Yes We Can do That and yes i forgot that intead of locals.add(a[i][j]) , we need tow write locals.add(i+j) Hope its fine now :) *Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/FKYupw3YSG4J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: matrix sum
question is based on simple D.P. use an auxiliary matrix to record the sum of all rectangles we are possible and use this matrix in subsequent quering there is an example 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 this is our original matrix now keep on doing the sum on auxiliary matrix aux[i][j]=aux[i-1][j]+aux[i][j-1]+original[i][j] this is the relation . hope this helps correct me if i m wrong. On Tue, Dec 14, 2010 at 2:52 PM, juver++ avpostni...@gmail.com wrote: O(nm) preprocessing is required. A[i][j] contains sum of all numbers which lies into a rectangle with bottom right corner at (i, j). To answer the query: decompose rectangles and find the answer via some addition and subtractions. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.