Maximum Sum of Subsequence with Non-Adjacent Elements in Java
Maximum Sum of Subsequence with Non-Adjacent Elements in Java
In this tutorial, we are going to find maximum sum of subsequence with non-adjacent elements in Java. Finding the greatest sum of a subsequence where no element is present at consecutive locations in an integer array is the task at hand.
Examples:
Example 1:
Input: arr = [4, 1, 1, 4, 2, 1]
Output: 9
Explanation:
We start with the first element, 4.
Skipping the next element, we move to the third element which is also 4.
Lastly, we add the sixth element, which is 1.
Sum = 4 + 4 + 1 = 9
Example 2:
Input: arr = [10, -1, -2, -3, 2]
Output: 12
Explanation:
We start with the first element, 10.
Skipping the next three elements, we move to the fifth element, which is 2.
Sum = 10 + 2 = 12
Example 3:
Input: arr = [3, 2, 5, 10, 7]
Output: 15
Explanation:
We start with the first element, 3.
Skipping the next element, we move to the third element, which is 5.
Lastly, we add the fifth element, which is 7.
Sum = 3 + 5 + 7 = 15
Example 4:
Input: arr = [5, 5, 10, 100, 10, 5]
Output: 110
Explanation:
We start with the first element, 5.
Skipping the next element, we move to the third element, which is 10.
Skipping the next element, we move to the fifth element, which is 100.
Sum = 5 + 100 + 5 = 110
Example 5:
Input: arr = [1, 2, 3, 4, 5, 6, 7, 8]
Output: 20
Explanation:
We start with the first element, 1.
Skipping the next element, we move to the third element, which is 3.
Skipping the next element, we move to the fifth element, which is 5.
Lastly, we add the seventh element, which is 7.
Sum = 1 + 3 + 5 + 7 = 16
Approach 1: Using recursive approach
ALGORITHM:
Step 1: Create a recursive function that will search through all potential subsequences and identify the one with the highest sum.
Step 2: Add the value of the current element to the result of the recursive call.
Step 3: Make use of the recursive function to advance to the next element.
Step 4: Define a method which initializes the recursive process by invoking it and starting from index 0.
Filename: NonAdjacentElements.java
import java.util.*; public class NonAdjacentElements { // A function to determine the highest possible sum static int rec(int numbers[], int index,int length) { if (index >= length) return 0; return Math.max(numbers[index] + rec(numbers, index + 2, length), rec(numbers, index + 1, length)); } // A function to determine the highest possible total static int calculateMaximumSum(int[] array, int length) { return rec(array, 0, length); } public static void main(String args[]) { // Creating the sample array int[] array = {4, 1, 1, 4, 2, 1}; int length = 6; System.out.println(calculateMaximumSum(array, length)); } }
Output:
9
Complexity analysis:
Time complexity: O(2N), in where N is the total number of elements in A.
Space complexity: O(N) It is stack space that is recursive.
Approach 2: Using dynamic programming
ALGORITHM:
Step 1: Make an array of integers.
Step 2: Set each element's initial value to indicate that it hasn't been calculated yet.
Step 3: Construct a recursive function that accepts the numerical list.
Step 4: Make a list using the provided components.
Step 5: Determine the list and store sizes.
Step 6: Print the result
Filename: SubsequenceElements.java
import java.util.*; public class SubsequenceElements { // A function to determine the highest possible sum public static int rec(Listnumbers, int index, int[] memo) { if (index >= numbers.size()) { return 0; } // Return the result of the current index computation if it has already been calculated. if (memo[index] != -1) { return memo[index]; } memo[index] = Math.max(rec(numbers, index + 1, memo), numbers.get(index) + rec(numbers, index + 2, memo)); return memo[index]; } public static int calculateMaximumSum(List numbers, int length) { int[] memo = new int[length + 1]; Arrays.fill(memo, -1); return rec(numbers, 0, memo); } public static void main(String[] args) { // Creating the array List array = Arrays.asList(10, -1, -2, -3, 2); int length = array.size(); System.out.println(calculateMaximumSum(array, length)); } }
Output:
12
Complexity analysis:
Time complexity: The time complexity of the program is O(N).
Space complexity: Recursive stack space is represented by O(N)+O(N), and memo arrays are represented by O(N)+O(N).