CODEWITHSUNDEEP
algorithmdynamic-programming
GeT_RiGhT
GeT_RiGhT

Reputation: 21

Maximum sum of all contiguous subarrays of prime length

I was recently asked this question in an interview,

Given an array of non-negative integers find the maximum cumulative sum that could be obtained such that the length of all the participating subarray is a prime number. I tried to come up with a solution for this using Dynamic Programming but unfortunately could not.

Eg: If the array is [9,8,7,6,5,4,3,1,2,2] it should return 46 (sum of the subarray [9,8,7,6,5,4,3] of length 7 and [2,2] of length 2). You cannot combine [9,8,7,6,5,4,3] and [1,2,2] since it would result in a contiguous subarray (idempotency) of length 10 which is non prime.

Can anyone explain how to solve such problems using DP? Thanks.

Upvotes: 2

Views: 1089

Answers (3)

גלעד ברקן
גלעד ברקן

Reputation: 23945

How about something like this (approximately) O(n * n / log n) time, O(n) space, DP?

Let f(i) represent the greatest sum up to index i where a[i] is either excluded from a contiguous subset or is the last of a subset of prime length. Then:

f(i) = sum(a[0]...a[i]) if (i + 1) is prime, otherwise
  max(
    // a[i] excluded
    f(i-1),
    f(i-2),

    // a[i] is last of a subset
    sum(a[i - primes[j] + 1]...a[i]) + f(i - primes[j] - 1) 
      for primes[j] <= i
  )

(Summing the intervals can be done in O(1) time with O(n) preprocessing of prefix-sums.)

Upvotes: 1

pseudo_teetotaler
pseudo_teetotaler

Reputation: 1575

Since others have solved the problem for non-negative integers.

But if you have -ve numbers also, then also this algorithm will work. I think you have to slightly tweak Kadane's Algo.

Following are the changes for modified Kadane's Algo. All lines marked ** are changes. 

Initialize:
    max_so_far = 0
    max_ending_here = 0
   ** MAX_SO_FAR_FOR_PRIMES =0
   ** SUB_ARRAY_SIZE = 0

Loop for each element of the array
   max_ending_here = max_ending_here + a[i]
   ** SUB_ARRAY_SIZE = SUB_ARRAY_SIZE + 1 // since a[i] included in subarray, increase sub_array_size
  if(max_ending_here < 0)
            max_ending_here = 0
   **         SUB_ARRAY_SIZE = 0  
  if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
   ** if(MAX_SO_FAR_FOR_PRIMES < max_ending_here && isPrime(SUB_ARRAY_SIZE)) // comparing when SUB_ARRAY_SIZE is Prime.
   **      MAX_SO_FAR_FOR_PRIMES = max_ending_here.    

return MAX_SO_FAR_FOR_PRIMES

Basically, take one more variable MAX_SO_FAR_FOR_PRIMES, which keeps the maximum sum subarray for prime sized subarray so far.

Also store the SUB_ARRAY_SIZE, which stores the size of the sub-array anytime during looping.

Now just compare you MAX_SO_FAR_FOR_PRIMES with your max_ending_here whenever the SUBARRAY_SIZE is prime. And update `MAX_SO_FAR_FOR_PRIMES1 accordingly.

Upvotes: 0

ChatterOne
ChatterOne

Reputation: 3541

What you can do:

  • take the length of the list and go back until you find a prime number
  • get a window of elements and sum them
  • check if it's the maximum sum and in case it is, store it
  • go to the next window

This works because of the constraint that all integers are positive, it would not work otherwise.

Basically something like this (very roughly, in pseudo-python, obviously not tested):

input_list = (8, 1, 3, 4, 5, 2)
list_size = len(input_list)

while (list_size):
    if (is_prime(list_size)):
        window_size = list_size
        break
    list_size--

max_sum = -1
for i in xrange(0, list_size - window_size):
    current_sum = sum(input_list[i:i+window_size])
    if (max_sum < current_sum):
        max_sum = current_sum

print max_sum

Upvotes: 1

Related Questions