----------------------------------- bbi5291 Sat Sep 19, 2009 10:31 am Dynamic max subvector sum ----------------------------------- OK, here's a nice problem for those of you very algorithmically inclined: You are given a vector of 100000 numbers and 100000 commands to be executed in order. There are two types of commands. * Modify command: Specifies an index into the vector and a value to which to change the current value of the element at the specified index. For example, it might be encoded as "M 3 -5", meaning to change the element at index 3 to -5. * Query command: Specifies two indices into the vector, in effect specifying a subvector of the original vector. For example, if the original vector were (1 -2 3 -4 5 -6) and zero-based, the indices 2 and 4 would specify the subvector starting at index 2 and ending at index 4, or (3 -4 5). Now given this subvector, you want to find its subvector such that the sum of the elements within is maximal, and report that maximal sum. For example, in the query given, the subvector of (3 -4 5) with the maximal sum is (5). Hence the answer to the query "Q 2 4" would be the sum of this subvector, which is merely 5. How do you solve this problem efficiently? Bits will be awarded for the solution to this difficult problem. Please be honest and don't use online resources. ----------------------------------- chopperdudes Mon Sep 21, 2009 9:06 pm RE:Dynamic max subvector sum ----------------------------------- i'm taking this requires more efficiency than merely dp'ing to find the subvector sum? might try if you include an input file. ----------------------------------- bbi5291 Mon Sep 21, 2009 9:59 pm Re: Dynamic max subvector sum ----------------------------------- Ahh, but then I'd have to specify an input format, which is annoying. The problem with the DP approach is that it takes linear time per query. With 100000 elements and 100000 queries, that will time out. ----------------------------------- Brightguy Thu Sep 24, 2009 11:54 am Re: Dynamic max subvector sum ----------------------------------- How about this (brief) sketch: Let x be the input vector of size n. Compute the running total y, i.e., y(i) = sum(x(1..i)). Solving the query "Q p q" is equivalent to finding the largest "jump" in y(p..q), i.e., finding the best "jump indices" i and j>i such that y(j)−y(i) is maximized and p