tag:blogger.com,1999:blog-6314876008291942531.post398044561348628428..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: Maximum sub-array sumUnknownnoreply@blogger.comBlogger4125tag:blogger.com,1999:blog-6314876008291942531.post-48213469794951270082011-09-29T22:30:13.464-07:002011-09-29T22:30:13.464-07:00[i...j]=6 is not maximum[i...j]=6 is not maximumcodingplaygroundhttps://www.blogger.com/profile/08478993186814330588noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-69420085980855621922011-09-29T17:15:41.015-07:002011-09-29T17:15:41.015-07:00@codingplayground
I disagree with your point 1. C...@codingplayground<br /><br />I disagree with your point 1. Consider the following sequence:<br />1,-15,10,5,5<br />you can see that the sub-array [k+1...j] = 15 is larger than the sub-array [i..j] = 6MonkeyLasheshttps://www.blogger.com/profile/09452108925819738790noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-45364620836644438792009-02-11T05:03:00.000-08:002009-02-11T05:03:00.000-08:00About the linear solution. Consider the sub-array ...About the linear solution. Consider the sub-array with maximum sum [i... j]. then<BR/><BR/>1. Any sub-array [i... k] with i <= k < j must be positive, otherwise the subarray [k+1 ... j] would have a sum larger than the one of the sub-array [i...j] and this is a contradiction.<BR/><BR/>2. There exist an l : 1 <= l < i such that the sub-array [l ... i-1] has negative sum, otherwise the sub-array [l ... j] would have a sum larger than the one [i ... j] and this is a contradiction. <BR/><BR/>As a consequence during a linear scan when the num is negative or zero, we can safely start a new segmentcodingplaygroundhttps://www.blogger.com/profile/08478993186814330588noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-6710471713088802262009-02-10T22:43:00.000-08:002009-02-10T22:43:00.000-08:00I like this problem. The naive solution is exponen...I like this problem. The naive solution is exponential. The less naive solution is quadratic, but there is a smart linear solution.codingplaygroundhttps://www.blogger.com/profile/08478993186814330588noreply@blogger.com