wu :: forums « wu :: forums - Finding sub Array having Maximum Sum » Welcome, Guest. Please Login or Register. Nov 25th, 2024, 11:49am

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    cs (Moderators: towr, william wu, Grimbal, SMQ, ThudnBlunder, Eigenray, Icarus)    Finding sub Array having Maximum Sum « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Finding sub Array having Maximum Sum  (Read 691 times) nitin_162 Newbie     Gender: Posts: 33 Finding sub Array having Maximum Sum   « on: Nov 15th, 2007, 6:47am » Quote Modify A 2-Dimensional array of +ve and -ve integers is given. Find a subArray having maximum sum of the elements in   efficient time. IP Logged SMQ wu::riddles Moderator Uberpuzzler     Gender: Posts: 2084 Re: Finding sub Array having Maximum Sum   « Reply #1 on: Nov 15th, 2007, 7:27am » Quote Modify We've seen this several times...  it's solvable in O(n) time and O(1) memory.  The key is to ask for each element in order, if it is better to keep the previous sequence or to start over with this element.   --SMQ IP Logged --SMQ towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Finding sub Array having Maximum Sum   « Reply #2 on: Nov 15th, 2007, 8:13am » Quote Modify That's for a one-dimensional array, isn't it? Two dimensions is a bit trickier, as I recall.. IP Logged Wikipedia, Google, Mathworld, Integer sequence DB bbskill Newbie     Posts: 42 Re: Finding sub Array having Maximum Sum   « Reply #3 on: Nov 15th, 2007, 8:24am » Quote Modify interesting, How to do with  Two dimensions? IP Logged SMQ wu::riddles Moderator Uberpuzzler     Gender: Posts: 2084 Re: Finding sub Array having Maximum Sum   « Reply #4 on: Nov 15th, 2007, 8:42am » Quote Modify on Nov 15th, 2007, 8:13am, towr wrote: That's for a one-dimensional array, isn't it? Two dimensions is a bit trickier, as I recall.. True, that.   --SMQ IP Logged --SMQ nitin_162 Newbie     Gender: Posts: 33 Re: Finding sub Array having Maximum Sum   « Reply #5 on: Nov 15th, 2007, 7:13pm » Quote Modify Is it something like subset sum problem which is NP Hard..?? IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Finding sub Array having Maximum Sum   « Reply #6 on: Nov 16th, 2007, 12:10am » Quote Modify on Nov 15th, 2007, 7:13pm, nitin_162 wrote: Is it something like subset sum problem which is NP Hard..?? No, this problem can definitely be solved in polynomial time (there's a trivial O(M2N2) solution, where you just look at all subarrays). IP Logged Wikipedia, Google, Mathworld, Integer sequence DB aditi Newbie     Posts: 17 Re: Finding sub Array having Maximum Sum   « Reply #7 on: Nov 16th, 2007, 10:04am » Quote Modify There is a O(n^3) solution to this problem at http://www.cc.gatech.edu/~kalyan/papers/mss-ppl95.pdf IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board