hi @all: i am little bit confused on the discussion going here on this thread.. largest subset sum problem in computer science is NP complete as followed http://en.wikipedia.org/wiki/Subset_sum_problem
also in book written by CLRS in chapter 35.5 i have found that "The decision problem ask whether there exist a subset of a set S that add up exactly target value t is NP complete problem.." the problem is solvable only when there are positives number are given as fo llowing link explains: http://genomics10.bu.edu/mschaff/microarraypapers/PDF-PowerPoint%20Presentations/Dynamic%20Programming.pdf and kadane algorithm is to find out the subset of just largest positive sum, not of finding the largest subset having sum equal to particular k. your me ntioned problem is same as that you want to find out the avg greater than k. so at any state if kadane founds curr_sum < 0 it set curr_sum = 0 retaining the sum as prev positive sum. but consider the extension of kadane for following array: {10 10 10 10 -50 200 -100 -100 -100} here at index 3 avg goes less than suppose 5 but we can't discard the subarray for for further because you can see that 10 10 10 10 -50 200 is giving the largest subarray having avg greater than 5 i am not sure about my comment here.. pls correct me if i am wrong... On Sat, Nov 24, 2012 at 12:37 AM, Sachin Chitale <[email protected]>wrote: > @ bharat, koup > > Sorry I missed this condition... > Algo can tweaked little bit further to cover all conditions.. > Algorithm--> > 1. Find out start and end index of contiguous subarray which* has sum >0 * > O(n) > 2.Once u have start and end index calculate avg if it satisfies the > condition then done O(n) > 2.1 other wise run a loop through start to end index and remove trailing > elements by increasing start > 2.2 simultaneously check avg..this will lead to proper subarray. > 3. In similar fashion start reducing end valuse keeping start > constant.....do it sub steps of 2... > > Check out the code...Time Com.. O(n) Space O(1) > compare result of 2 and 3 and choose d best one... > > public class LongestConArrMaxAvg{ > static int maxAvgSum(int a[], float k) { > int max_so_far = 0, max_ending_here = 0, avg = 0, s = -1, e = -1, ts, te, > tsum; > boolean flag = false; > > for (int i = 0; i < a.length; i++) { > > if (max_ending_here == 0) > s = e = i; > > max_ending_here = max_ending_here + a[i]; > > if (max_ending_here < 0) { > max_ending_here = 0; > s = e = -1; > } > if ( max_ending_here>0) { > max_so_far = max_ending_here; > > e = i; > } > > } > > if (avgGreater(max_so_far, s, e, k)){ > System.out.println("Result subarray start index:" + s > + " End index:" + e); > return max_so_far; > } > /*This will generate two sequence use optimal time complexity of this algo > is O(n) > * > * > */ > if (s >= 0 && !avgGreater(max_so_far, s, e, k)) { > max_ending_here = max_so_far; > ts = s; > te = e; > > while (ts < te) { > > max_ending_here -= a[ts]; > if (avgGreater(max_ending_here, ts+1, te, k)) { > ts++; > System.out.println("Result subarray start index:" + ts > + " End index:" + te); > break; > } > ts++; > } > ts = s; > te = e; > max_ending_here = max_so_far; > while (ts < te) { > > max_ending_here -= a[te]; > if (avgGreater(max_ending_here, ts, te-1, k)) { > te--; > System.out.println("Result subarray start index:" + ts > + " End index:" + te); > break; > } > te--; > } > > } > > return max_so_far; > } > > static boolean avgGreater(int sum, int s, int e, float k) { > float t= (float) (sum / (e - s + 1)); > return t>=k? true : false; > } > > public static void main(String[] args) { > > int[] a = {7,10,-1}; > maxAvgSum(a, 5); > } > > } > > > On Fri, Nov 23, 2012 at 4:14 PM, bharat b <[email protected]>wrote: > >> @ sachin : again u misunderstood the question .. question says *longest*.. >> >> As per u'r algo .. >> 1. Find out start and end index of contiguous subarray which has max sum >> O(n) >> 2.Once u have start and end index calculate avg if it satisfies the >> condition then done O(n) >> *NO -- > even if it satisifies, that may not be the longest * >> *Ex: {7,10,-1} and k=5 => as per u'r algo .. ans would be {7,10}-> avg >> is >5. But and is {7,10,-1}-> avg is >5.* >> >> >> >> On Wed, Nov 21, 2012 at 11:51 PM, Sachin Chitale < >> [email protected]> wrote: >> >>> Implementation >>> >>> public class Kadanes { >>> static int maxAvgSum(int a[], float k) { >>> int max_so_far = 0, max_ending_here = 0, avg = 0, s = -1, e = -1, ts, >>> te, tsum; >>> boolean flag = false; >>> >>> for (int i = 0; i < a.length; i++) { >>> >>> if (max_ending_here == 0) >>> s = e = i; >>> >>> max_ending_here = max_ending_here + a[i]; >>> >>> if (max_ending_here < 0) { >>> max_ending_here = 0; >>> s = e = -1; >>> } >>> if (max_so_far < max_ending_here) { >>> max_so_far = max_ending_here; >>> >>> e = i; >>> } >>> >>> } >>> >>> if (avgGreater(max_so_far, s, e, k)){ >>> System.out.println("Result subarray start index:" + s >>> + " End index:" + e); >>> return max_so_far; >>> } >>> /*This will generate two sequence use optimal time complexity of this >>> algo is O(n) >>> * >>> * >>> */ >>> if (s >= 0 && !avgGreater(max_so_far, s, e, k)) { >>> max_ending_here = max_so_far; >>> ts = s; >>> te = e; >>> >>> while (ts < te) { >>> >>> max_ending_here -= a[ts]; >>> if (avgGreater(max_ending_here, ts+1, te, k)) { >>> ts++; >>> System.out.println("Result subarray start index:" + ts >>> + " End index:" + te); >>> break; >>> } >>> ts++; >>> } >>> ts = s; >>> te = e; >>> max_ending_here = max_so_far; >>> while (ts < te) { >>> >>> max_ending_here -= a[te]; >>> if (avgGreater(max_ending_here, ts, te-1, k)) { >>> te--; >>> System.out.println("Result subarray start index:" + ts >>> + " End index:" + te); >>> break; >>> } >>> te--; >>> } >>> >>> } >>> >>> return max_so_far; >>> } >>> >>> static boolean avgGreater(int sum, int s, int e, float k) { >>> float t= (float) (sum / (e - s + 1)); >>> return t>=k? true : false; >>> } >>> >>> public static void main(String[] args) { >>> >>> int[] a = { 100, 10, -1, -1, 4, -1, 7, 2, 8 }; >>> System.out.println(maxAvgSum(a, 5)); >>> } >>> } >>> >>> >>> On Wed, Nov 21, 2012 at 10:07 PM, Sachin Chitale < >>> [email protected]> wrote: >>> >>>> Hello, >>>> >>>> Algorithm--> >>>> 1. Find out start and end index of contiguous subarray which has max >>>> sum O(n) >>>> 2.Once u have start and end index calculate avg if it satisfies the >>>> condition then done O(n) >>>> 2.1 other wise run a loop through start to end index and remove >>>> trailing elements by increasing start >>>> 2.2 simultaneously check avg..this will lead to proper subarray. >>>> 3. In similar fashion start reducing end valuse keeping start >>>> constant.....do it sub steps of 2... >>>> >>>> compare result of 2 and 3 and choose d best one... >>>> give me some time to write code.... >>>> >>>> >>>> On Wed, Nov 21, 2012 at 12:29 AM, Koup <[email protected]> wrote: >>>> >>>>> To be correct I need the longest subarray that has an average greater >>>>> than k but my main problem here is to find the longest one. Thank you ! >>>>> >>>>> -- >>>>> >>>>> >>>>> >>>> >>>> >>>> >>>> -- >>>> Regards, >>>> Sachin Chitale >>>> Application Engineer SCJP, SCWCD >>>> Contact# : +91 8086284349, 9892159511 >>>> Oracle Corporation >>>> >>> >>> >>> >>> -- >>> Regards, >>> Sachin Chitale >>> Application Engineer SCJP, SCWCD >>> Contact# : +91 8086284349, 9892159511 >>> Oracle Corporation >>> >>> -- >>> >>> >>> >> >> -- >> >> >> > > > > -- > Regards, > Sachin Chitale > Application Engineer SCJP, SCWCD > Contact# : +91 8086284349, 9892159511 > Oracle Corporation > > -- > > > -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, India<http://www.iitkgp.ac.in/> Mobile No: +91-8798049298, +91-9424738542 Alternate Email: [email protected] [image: Linkedin]<http://www.linkedin.com/profile/view?id=106245716&trk=tab_pro> [image: Twitter] <https://twitter.com/rahulkumarpatle> <https://www.facebook.com/rkpatle> --
