CODEWITHSUNDEEP
algorithmsequencedynamic-programming
user1885433
user1885433

Reputation:

Find contiguous subsequences such that cube of the sum of numbers is at most y

I am given a sequence of numbers A[1..n] and a fixed number y. The sequence may contain negative values. My algorithm should be able to decide whether the sequence can be partitioned into contiguous subsequences such that cube of the sum of numbers in each subsequence is at most y. Here's my initial answer:

enter image description here

I believe this algorithm is reasonable, but I'd like to hear your opinions before moving forward with memoization. Any help would be appreciated.

Upvotes: 0

Views: 485

Answers (2)

Paul Hankin
Paul Hankin

Reputation: 58320

Your algorithm is correct, but it's O(n^2) rather than O(n).

To improve it, you can use this:

minsum([]) = 0
minsum(xs + [x]) = minsum(xs) + x if minsum(xs)^3 > y
                 = min(minsum(xs) + x, x) otherwise.

This finds a partition of the list such that each part has sum-cubed <= y, except for the last which just has the sum as small as possible. The function returns this minimum sum of the last part of the partition.

This formulation of the problem gives you an iterative solution, which you can consider a form of dynamic programming, since the solution at step n depends on the solution at step n-1.

def exists_partition(xs, y):
   m = 0
   for x in xs:
       m = m + x if m**3 > y else min(m + x, x)
   return m**3 <= y

Upvotes: 1

barak manos
barak manos

Reputation: 30136

Given your description, you obviously don't need to repeatedly calculate cubes.

Instead, you can calculate the 3rd root of y once, and then pass it to your function.

Here is the recursive way of doing it (although dynamic programming might prove a lot more efficient). The solution below assumes that the input sequence contains only integer values, but it can be easily converted to take a sequence of rational values:

bool Partition(int values[],int numOfValues,int root3_y)
{
    for (int i=1; i<numOfValues; i++)
    {
        if (Partition(values,i,root3_y) && Partition(values+i,numOfValues-i,root3_y))
            return true;
    }
    int sum = 0;
    for (int i=0; i<numOfValues; i++)
        sum += values[i];
    return sum <= root3_y;
}

Upvotes: 0

Related Questions