Given an array Arr of size N containing positive integers. Find the maximum sum of a any possible subsequence such that no two numbers in the subsequence should be adjacent in Arr.
Question
Given an array Arr of size N containing positive integers. Find the maximum sum of a any possible subsequence such that no two numbers in the subsequence should be adjacent in Arr.
Solution
To find the maximum sum of a subsequence with the given condition, we can use dynamic programming.
- Initialize two variables, prevMaxSum and currMaxSum, both set to 0.
- Iterate through the array Arr from left to right.
- For each element Arr[i], calculate the maximum sum considering two cases: a. If the previous element (Arr[i-1]) is included in the subsequence, then the current maximum sum would be prevMaxSum + Arr[i]. b. If the previous element is not included in the subsequence, then the current maximum sum would be currMaxSum.
- Update prevMaxSum to currMaxSum and currMaxSum to the maximum value between the two cases calculated in step 3.
- Repeat steps 3 and 4 until the end of the array.
- The final value of currMaxSum will be the maximum sum of the subsequence.
Here is the implementation in Python:
def maxSumSubsequence(Arr):
n = len(Arr)
prevMaxSum = 0
currMaxSum = 0
for i in range(n):
temp = max(prevMaxSum + Arr[i], currMaxSum)
prevMaxSum = currMaxSum
currMaxSum = temp
return currMaxSum
# Example usage
Arr = [1, 2, 3, 4, 5]
maxSum = maxSumSubsequence(Arr)
print("Maximum sum of subsequence:", maxSum)
In this example, the maximum sum of a subsequence without adjacent numbers is 9, which is achieved by selecting the numbers 1, 3, and 5.
Similar Questions
Given an array of n positive integers. Find the sum of the maximum sum subsequence of the given array such that the integers in the subsequence are sorted in strictly increasing order i.e. a strictly increasing subsequence. Example 1:Input: N = 5, arr[] = {1, 101, 2, 3, 100} Output: 106Explanation:The maximum sum of a increasing sequence is obtained from {1, 2, 3, 100},Example 2:Input: N = 4, arr[] = {4, 1, 2, 3}Output: 6Explanation:The maximum sum of a increasing sequence is obtained from {1, 2, 3}.Your Task: You don't need to read input or print anything. Complete the function maxSumIS() which takes N and array arr as input parameters and returns the maximum value.Expected Time Complexity: O(N2)Expected Auxiliary Space: O(N)Constraints:1 ≤ N ≤ 1031 ≤ arr[i] ≤ 105
Given an integer array arr, write a program to find the subarray which has the largest sum and return its sum. If the array is empty, return 0.Sample Input:9-2 -1 -3 4 -1 2 1 -5 4Sample Output: 6Explanation:The subarray is [4, -1, 2, 1] and the sum is 6
You are given an array nums consisting of integers. You are also given a 2D array queries, where queries[i] = [posi, xi].For query i, we first set nums[posi] equal to xi, then we calculate the answer to query i which is the maximum sum of a subsequence of nums where no two adjacent elements are selected.Return the sum of the answers to all queries.Since the final answer may be very large, return it modulo 109 + 7.A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements. Example 1:Input: nums = [3,5,9], queries = [[1,-2],[0,-3]]Output: 21Explanation:After the 1st query, nums = [3,-2,9] and the maximum sum of a subsequence with non-adjacent elements is 3 + 9 = 12.After the 2nd query, nums = [-3,-2,9] and the maximum sum of a subsequence with non-adjacent elements is 9.Example 2:Input: nums = [0,-1], queries = [[0,-5]]Output: 0Explanation:After the 1st query, nums = [-5,-1] and the maximum sum of a subsequence with non-adjacent elements is 0 (choosing an empty subsequence). Constraints:1 <= nums.length <= 5 * 104-105 <= nums[i] <= 1051 <= queries.length <= 5 * 104queries[i] == [posi, xi]0 <= posi <= nums.length - 1-105 <= xi <= 105
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Write a program for the maximum possible difference between two subsets of an array.Given an array of n integers. The array may contain repetitive elements, but the highest frequency of any element must not exceed two. Make two subsets such that the difference of the sum of their elements is maximum and both of them jointly contain all elements of the given array along with the most important condition, no subset should contain repetitive elements. ExampleInput:45 8 -1 4Output:Maximum Difference = 18Explanation:Suppose arr[ ] = {5, 8, -1, 4}Let Subset A = {5, 8, 4} & Subset B = {-1}Sum of elements of subset A = 17, of subset B = -1Difference of Sum of Both subsets = 17 - (-1) = 18Input format :The first input line consists of the size of an array, n.The second input consists of the array elements, separated by space.Output format :The output displays the maximum possible difference between two subsets of an array.Refer to the sample output for the formatting specifications.Code constraints :2 ≤ n ≤ 100Sample test cases :Input 1 :74 2 -3 3 -2 -2 8Output 1 :Maximum Difference = 20Input 2 :45 8 -1 4Output 2 :Maximum Difference = 18
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.