tag:blogger.com,1999:blog-5799246.post113181346005818352..comments2023-02-23T12:50:08.443+00:00Comments on a very occasional diary @ Nikita Danilov: An exercisenikitahttp://www.blogger.com/profile/09403336533089968821noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-5799246.post-1133980161900736192005-12-07T18:29:00.000+00:002005-12-07T18:29:00.000+00:00When trying to implement the algorith for my proof...When trying to implement the algorith for my proof, I've noticed that I've not considered that i <= j, so the algorithm won't be that simple (I haven't found a way to assure i <= j without needing most parts of the original proof you presented).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5799246.post-1133876823101713312005-12-06T13:47:00.000+00:002005-12-06T13:47:00.000+00:00Eduardo,your proof is correct (and elegant too), b...Eduardo,<BR/><BR/>your proof is correct (and elegant too), but it is a correctness proof for a <B>different</B> algorithm. Can you construct it? :-)nikitahttps://www.blogger.com/profile/09403336533089968821noreply@blogger.comtag:blogger.com,1999:blog-5799246.post-1133874472702909912005-12-06T13:07:00.000+00:002005-12-06T13:07:00.000+00:00I was thinking on a simpler proof:Given a sub-arra...I was thinking on a simpler proof:<BR/><BR/>Given a sub-array A(i,j) of A(0,n-1), we may prove that:<BR/><BR/>S(0,n-1) = S(0,i-1) + S(i,j) + S(j+1, n-1)<BR/><BR/>So, just find 'i' that minimizes S(0,i-1) (can be solved with one pass), and the j that minimizes S(j+1, n-1) (can be solved with one pass, too (by maximizing S(0,j))).<BR/><BR/>It seems simpler to me, so we didn't need all the subarray-overlapping and outfix/infix logic.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5799246.post-1132154285395207232005-11-16T15:18:00.000+00:002005-11-16T15:18:00.000+00:00An update (with a proof of correctness) posted.An update (with a proof of correctness) <A HREF="http://nikitadanilov.blogspot.com/2005/11/exercise.html" REL="nofollow">posted</A>.nikitahttps://www.blogger.com/profile/09403336533089968821noreply@blogger.comtag:blogger.com,1999:blog-5799246.post-1131919365632053212005-11-13T22:02:00.000+00:002005-11-13T22:02:00.000+00:00Well, basically I came up with that solution by im...Well, basically I came up with that solution by imagining the array as a xy-plot with the indexes running on the x-axis and the values on the y-axis. Then I noticed that if the current sum drops below zero, it is no use to keep summing from the previous "start index" as we would just start out with a negative value. Thus, we can just instead start a new sum from the next index. And so on until we find a positive integer again.<BR/><BR/>Of course, we must still keep the previous "start index" in case we don't find any ranges with bigger sums later on.<BR/><BR/>If all the integers in the array are negative, the range with the biggest sum consists of only the largest individual element.<BR/><BR/>Not sure if Jerome's interpretation is correct since I'm too lazy to decipher it ;pAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-5799246.post-1131907957490355552005-11-13T18:52:00.000+00:002005-11-13T18:52:00.000+00:00Not sure why I tried to make them with a fixed siz...Not sure why I tried to make them with a fixed size...<BR/><BR/>Matti's solution seems the right one.<BR/><BR/>The algorythm idea comes from the observation that:<BR/><BR/>with a[i, k] a sub-array of a[0, n] and sum(a[i, k]) the sum of the elements between index i and k included<BR/><BR/>for all i, j, k € [0, n-1] such as i<=j<=k<BR/><BR/>sum(a[i, k]) = sum(a[i, j - 1]) + sum(a[j, k])<BR/><BR/>if sum(a[i, j - 1]) < 0<BR/> then sum(a[j, k]) > sum(a[i, k]).<BR/><BR/>[So many years I haven't done theorical maths, so feel free to correct me :) ]Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5799246.post-1131886135135190072005-11-13T12:48:00.000+00:002005-11-13T12:48:00.000+00:00to VinceLeg:if no negative numbers are in the arra...to VinceLeg:<BR/><BR/><I>if no negative numbers are in the array to start with</I><BR/><BR/>that's a big "if" :-)nikitahttps://www.blogger.com/profile/09403336533089968821noreply@blogger.comtag:blogger.com,1999:blog-5799246.post-1131883392734478652005-11-13T12:03:00.000+00:002005-11-13T12:03:00.000+00:00Of all possible sub arrays, there is one and only ...Of all possible sub arrays, there is one and only one of size N, and it seems to have the biggest sum, if no negative numbers are in the array to start with...<BR/><BR/>subarray = (1,N)<BR/><BR/>And if I remember properly, it's O(1), no need to pass over the array's elements.<BR/>:P<BR/><BR/>Or maybe I'm full of it, and didn't translate correctly the exercise to my native language.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5799246.post-1131835769907223702005-11-12T22:49:00.000+00:002005-11-12T22:49:00.000+00:00C code:----------void find_largest_sub(int *a, uns...C code:<BR/>----------<BR/><BR/>void find_largest_sub(int *a, unsigned int len)<BR/>{<BR/> unsigned int i, start = 0, end = 0, new_start = 0;<BR/> int max = -2147483648, sum = 0;<BR/> <BR/> for (i = 0; i < len; i++) {<BR/> sum += a[i];<BR/> <BR/> if (sum >= max) {<BR/> start = new_start;<BR/> end = i;<BR/> max = sum;<BR/> }<BR/> <BR/> if (sum < 0) {<BR/> sum = 0;<BR/> new_start = i + 1;<BR/> }<BR/> }<BR/> printf("Subarray ranges from %d to %d\n", start, end);<BR/>}<BR/><BR/>Seemed easy and worked in my few tests, but did I miss something?<BR/><BR/>If there is need to sum big integers one could of course just use longer integers for the counters.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5799246.post-1131826743563561212005-11-12T20:19:00.000+00:002005-11-12T20:19:00.000+00:00Did I miss something?Your solution only considers ...<I>Did I miss something?</I><BR/><BR/>Your solution only considers sub-arrays of length n (3 in your code). Original question was to find maximum among <EM>all</EM> possible sub-arrays, sorry if that wasn't clear enough.nikitahttps://www.blogger.com/profile/09403336533089968821noreply@blogger.comtag:blogger.com,1999:blog-5799246.post-1131826003682995662005-11-12T20:06:00.000+00:002005-11-12T20:06:00.000+00:00off by one...s/a.length - n - 1/a.length - n/off by one...<BR/>s/a.length - n - 1/a.length - n/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5799246.post-1131825885784825522005-11-12T20:04:00.000+00:002005-11-12T20:04:00.000+00:00The idea is to keep track of the biggest sum and i...The idea is to keep track of the biggest sum and its index, and to compute the new sum by removing adding the difference between the first item of the last sub-array and the last of the next sub-array. Is that right?<BR/><BR/>N elements, more or less 2*N operations<BR/>5 temporary variables.<BR/><BR/>bsh code...<BR/><BR/>int n = 3;<BR/>int[] a = { 1, 2, 3, 2, 3, 1, 3, 2, 3, 1, 2, 3, 3, 3, 1, 1, 2, 3 };<BR/><BR/><BR/><BR/>int sum = 0;<BR/>int i;<BR/>for (i = 0; i < n; i++) {<BR/> sum += a[i];<BR/>}<BR/><BR/>int index_max_sum = 0;<BR/>int last_sum = sum;<BR/>int max_sum = last_sum;<BR/>for (i = 0; i < a.length - n - 1; i++) {<BR/> last_sum = last_sum - a[i] + a[i + n];<BR/> if (last_sum > max_sum) {<BR/> index_max_sum = i + 1;<BR/> max_sum = last_sum;<BR/> }<BR/>}<BR/><BR/>System.out.println("max sum " + max_sum);<BR/>System.out.println("index start sub-array " + index_max_sum);<BR/><BR/>Did I miss something?Anonymousnoreply@blogger.com