Maximum sum of a Subarray with prime integers in Java

Find the greatest sum of a continuous subarray such that the subarray only consists of prime numbers given an array arr[] of integers of size n. Stated a certain way, no non-prime integer is allowed to exist in the selected subarray.

Example 1:

Input:

int a[] = { 8, 1, 2, 4, 3, 7, 5, 11, 13 }

Output:

The maximum sum obtained from the prime sub-array is 39.

Explanation:

For the given array { 8, 1, 2, 4, 3, 7, 5, 11, 13 }, the prime subarray is given by { 3, 7, 5, 11, 13 } and the sum is (3 + 7 + 5 + 11 + 13 = 39). Hence, the maximum sum obtained from the prime sub-array is 39.

Example 2:

Input:

int a[] = { 1, 5, 8, 4, 7, 5, 1, 3, 7 }

Output:

The maximum sum obtained from the prime sub-array is 12.

Explanation:

For the given array { 1, 5, 8, 4, 7, 5, 1, 3, 7 }, the prime subarray is given by { 7, 5 } and the sum is (7 + 5 = 12). Hence, the maximum sum obtained from the prime sub-array is 12.

Example 3:

Input:

int a[] = { 8, 9, 7, 4, 4, 1, 10, 5, 6, 7 }

Output:

The maximum sum obtained from the prime sub-array is 7.

Explanation:

For the given array { 8, 9, 7, 4, 4, 1, 10, 5, 6, 7 }, the prime subarray is given by { 7 } and the sum is 7. Hence, the maximum sum obtained from the prime sub-array is 7.

Approach: Naïve Approach

The idea is to maintain track of the maximum total and check all potential subarrays that contain only prime numbers.

Algorithm:

Step 1: Set maxSum's initial value to 0.

Step 2: Go through each subarray in arr in a loop.

Step 2.1: Verify if the current subarray solely consists of prime numbers.

Step 2.1.1: In that case, calculate out its total.

Step 2.1.2: Update maxSum if its sum exceeds it.

Step 3: Return with maxSum.

Implementation:

FileName: MaxiSubArraySum.java

Output:

 
The maximum sum obtained from the prime sub-array is  39

Complexity Analysis:

The Time Complexity of the above code is O(N²*√N)), since we are first determining whether each integer in the subarray is prime, and then we are verifying all possible subarrays. The Space Complexity is O(1), which remains constant.

Approach: Efficient Approach

Creating a basic linear traversal is the strategy to follow. When a prime number appears, we continue to add to the existing sum, and we also update the maximum sum each time the current sum increases. We reset the current sum to 0 if we find a non-prime number.

Algorithm:

Step 1: Initialize the cur_Sum and max_Sum to 0.

Step 2: For every element present in the array, do the iteration.

Step 2.1: In the event that the element is a prime number

Step 2.1.1: Add it to cur_Sum.

Step 2.1.2: Modify max_Sum so that it equals the maximum of cur_Sum and max_Sum.

Step 2.2: If the element not be a prime number.

Step 2.2.1: Set cur_Sum back to zero.

Step 3: Give max_Sum back.

Step 4: Return the highest total obtained from the primary subarray.

Implementation:

FileName: EfficientMaxiSumSubArray.java

Output:

 
The maximum sum obtained from the prime sub-array  39

Complexity Analysis:

The Time Complexity is O(n√N), where N is the value of the highest element in the input array, and n is the number of elements in the array. The space complexity is O(1).