Given an array arr[] of measurement N, the duty is to search out the utmost subarray sum that may be obtained such that the size of the subarray must be prime.
Examples :
Enter: arr[] = {2, -1, 3, -2, 1, -1}
Output: 4
The subarray {2, -1, 3} of measurement = 3 (prime quantity)enter: arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}
Output: 7
The subarray {4, -1, -2, 1, 5} of measurement = 5 (prime quantity)
Naive Method: The thought is as follows:
Generate all attainable subarrays and from them discover those with prime size. Discover the utmost sum amongst them.
Observe the given steps to unravel the issue:
- Generate all attainable subarrays of all lengths utilizing nested for-loops.
- Discover the sum of every prime size subarray.
- The numbers that are primes could be precomputed by Sieve algorithm
- Now for every prime size, calculate the sum and take the utmost of it
Under is the implementation of the above strategy:
C++14
|
|
Time complexity: O(N3)
Auxiliary Area: O(N)
Environment friendly Method: To resolve the issue comply with the beneath concept:
Use Kadane’s algorithm, and replace the reply provided that the size of the subarray is prime.
Observe the given steps to unravel the issue:
- Initialize max_so_far = INT_MIN (since sum could be unfavourable), and max_ending_here = 0 (to maintain monitor of the present sum )
- Loop to iterate every component of the array:
- max_ending_here is the same as max_ending_here + arr[i]
- If max_so_far is lower than max_ending_here then replace max_so_far
- If max_ending_here is lower than 0 then set max_ending_here = 0
- Return max_so_far
- Now for calculating the subarray sum of prime size we’ve to maintain monitor of the subarray measurement and must examine whether or not the dimensions is prime or not
Under is the implementation of the above concept :
C++14
|
|
Time Complexity: O(N * log(logN))
Auxiliary Area: O(N)
