Given an array nums of length N which contains two types of numbers, one which has the value zero, the second which is a positive integer, the task is to collect numbers from the below operations and return the maximum value you can collect.
- If the given number is a positive integer, then it’s your choice, whether you can put it on the top of the queue or not.
- Else, if the number is zero, then pick the topmost number from the queue and remove it.
Examples:
Input: N = 7, nums = [1, 2, 3, 0, 4, 5, 0]
Output: 8
Explanation: To maximize the total value do the following operation while iterating the nums[ ]:
nums[0] = 1, put on the top of the queue. Queue becomes: [1]
nums[1] = 2, put on the top of the queue. Queue becomes: [2, 1]
nums[2] = 3, put on the top of the queue. Queue becomes: [3, 2, 1]
nums[3] = 0, pick the top value from the queue and remove it. Total val = 3, and queue becomes: [2, 1]
nums[4] = 4, put on the top of the queue. Queue becomes: [4, 2, 1]
nums[5] = 5, put on the top of the queue. Queue becomes: [5, 4, 2, 1]
nums[6] = 0, pick the top value from the queue and remove it. Total val = 3 + 5 = 8, and queue becomes: [4, 2, 1]
Return val = 8.Input: N = 8, nums = [5, 1, 2, 0, 0, 4, 3, 0]
Output: 11
Explanation: To maximize the total value do the following operation while iterating the nums[ ]:
nums[0] = 5, put on the top of the queue. Queue becomes: [5]
nums[1] = 1, ignore this number. Queue remains: [5]
nums[2] = 2, put on the top of the queue. Queue becomes: [2, 5]
nums[3] = 0, pick the top value from the queue and remove it. Total val = 0 + 2 = 2, and queue becomes: [5]
nums[4] = 0, pick the top value from the queue and remove it. Total val = 2 + 5 = 7, and queue becomes: [ ]
nums[5] = 4, put on the top of the queue. Queue becomes: [4]
nums[6] = 3, ignore this number. Queue remains: [4]
nums[7] = 0, pick the top value from the queue and remove it. Total val = 7 + 4 = 11, and queue becomes: [ ]
Return val = 11.
Approach: To solve the problem follow the below idea:
We will use a decreasing priority queue and store the positive integers in it, when we encounter zero we will take the peek() element (if it is not empty) from the priority queue and add it to the variable val.
Below are the steps for the above approach:
- Initialize a decreasing priority queue.
- Iterate the given array,
- If you encounter any positive integer, add it to the priority queue.
- Else, if you encounter a zero, check whether the priority queue is empty or not. If it is not empty, remove the top element from it and add it to the variable val which contains the current sum of the maximum value.
- Return the final answer val.
Below is the code for the above approach:
C++
// C++ code for the above approach#include <functional>#include <iostream>#include <queue>#include <vector>using namespace std;// Function to calculate maximum valueint calculateMaxVal(vector<int>& nums, int N){ priority_queue<int> decreasing; int val = 0; for (int i = 0; i < N; i++) { if (nums[i] == 0) { if (!decreasing.empty()) { val += (decreasing.top()); decreasing.pop(); } } else { decreasing.push(nums[i]); } } return val;}// Drivers codeint main(){ int N = 8; vector<int> nums = { 5, 1, 2, 0, 0, 4, 3, 0 }; cout << "Maximum value is: " << calculateMaxVal(nums, N) << endl; return 0;} |
Java
// Java code for the above approachimport java.util.*;class GFG { // Drivers code public static void main(String[] args) { int N = 8; int[] nums = { 5, 1, 2, 0, 0, 4, 3, 0 }; System.out.println("Maximum value is : " + calculateMaxVal(nums, N)); } // Function to calculate maximum value public static int calculateMaxVal(int[] nums, int N) { PriorityQueue<Integer> decreasing = new PriorityQueue<Integer>( Collections.reverseOrder()); int val = 0; for (int i = 0; i < N; i++) { if (nums[i] == 0) { if (!decreasing.isEmpty()) val += decreasing.remove(); } else { decreasing.add(nums[i]); } } return val; }} |
Python3
# Python code for the above approach:import heapq# Function to calculate maximum valuedef calculateMaxVal(nums): decreasing = [] val = 0 for num in nums: if num == 0: if decreasing: val += -heapq.heappop(decreasing) else: heapq.heappush(decreasing, -num) return valnums = [5, 1, 2, 0, 0, 4, 3, 0]print("Maximum value is: ", calculateMaxVal(nums))# This code is contributed by lokesh. |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class GFG { // Function to calculate maximum value static int CalculateMaxVal(List<int> nums, int N) { // Create a priority queue to store decreasing // numbers PriorityQueue<int> decreasing = new PriorityQueue<int>(new Comparison<int>( (x, y) => y.CompareTo(x))); int val = 0; // Iterate through the array for (int i = 0; i < N; i++) { // If the element is 0, pop the maximum element // from the priority queue and add it to the // result if (nums[i] == 0) { if (decreasing.Count > 0) { val += decreasing.Dequeue(); } } else { // If the element is non-zero, add it to the // priority queue decreasing.Enqueue(nums[i]); } } return val; } // Driver's code static void Main(string[] args) { // Input int N = 8; List<int> nums = new List<int>() { 5, 1, 2, 0, 0, 4, 3, 0 }; // Function call Console.WriteLine("Maximum value is: " + CalculateMaxVal(nums, N)); }}// Implementation of a priority queue using a heappublic class PriorityQueue<T> { private List<T> _heap; private Comparison<T> _comparison; public PriorityQueue() { _heap = new List<T>(); } public PriorityQueue(Comparison<T> comparison) { _heap = new List<T>(); _comparison = comparison; } public void Enqueue(T item) { _heap.Add(item); int i = _heap.Count - 1; while (i > 0) { int j = (i - 1) / 2; if (_comparison == null) { if (((IComparable<T>)_heap[j]) .CompareTo(item) <= 0) { break; } } else { if (_comparison(_heap[j], item) <= 0) { break; } } _heap[i] = _heap[j]; i = j; } _heap[i] = item; } public T Dequeue() { int lastIndex = _heap.Count - 1; T frontItem = _heap[0]; _heap[0] = _heap[lastIndex]; _heap.RemoveAt(lastIndex); --lastIndex; int i = 0; while (true) { int left = i * 2 + 1; if (left > lastIndex) { break; } int right = left + 1; if (right <= lastIndex && (_comparison == null ? ((IComparable<T>)_heap[left]) .CompareTo(_heap[right]) > 0 : _comparison(_heap[left], _heap[right]) > 0)) { left = right; } if (_comparison == null ? ((IComparable<T>)_heap[i]) .CompareTo(_heap[left]) <= 0 : _comparison(_heap[i], _heap[left]) <= 0) { break; } T tmp = _heap[i]; _heap[i] = _heap[left]; _heap[left] = tmp; i = left; } return frontItem; } public int Count { get { return _heap.Count; } }} |
Javascript
// Function to calculate maximum valuefunction calculateMaxVal(nums) { let decreasing = []; let val = 0; for (let i = 0; i < nums.length; i++) { if (nums[i] === 0) { if (decreasing.length > 0) { val += decreasing[0]; decreasing.shift(); } } else { decreasing.push(nums[i]); decreasing.sort((a, b) => b - a); } } return val;}// Driver codelet nums = [5, 1, 2, 0, 0, 4, 3, 0];console.log("Maximum value is: ", calculateMaxVal(nums));// akashish__ |
Output
Maximum value is : 11
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Approach 2: Greedy Algorithm
- Initialize two variables include and exclude as 0, representing the maximum sum including and the excluding the current element, respectively.
- Iterate through each element num in input array:
- Calculate the new value of include as the sum of the exclude and num.
- Update the value of exclude as the maximum of the include and exclude.
- The final result will be the maximum of the include and exclude.
Implementation :
C++
#include <iostream>#include <vector>#include <algorithm>int GFG(const std::vector<int>& arr) { int n = arr.size(); if (n == 0) return 0; if (n == 1) return arr[0]; std::vector<int> dp(n); dp[0] = arr[0]; dp[1] = std::max(arr[0], arr[1]); for (int i = 2; i < n; i++) { dp[i] = std::max(dp[i - 1], dp[i - 2] + arr[i]); } return dp[n - 1];}int maximizeSumGreedy(const std::vector<int>& arr) { int include = 0, exclude = 0; for (int num : arr) { int new_include = exclude + num; exclude = std::max(include, exclude); include = new_include; } return std::max(include, exclude);}int main() { std::vector<int> inputArray = {1, 2, 5, 4, 5}; int resultDP = GFG(inputArray); int resultGreedy = GFG(inputArray); std::cout << "Using Dynamic Programming:" << std::endl; std::cout << resultDP << std::endl; std::cout << "Using Greedy Algorithm:" << std::endl; std::cout << resultGreedy << std::endl; return 0;} |
Java
import java.util.List;class Main { public static int GFG(List<Integer> arr) { int n = arr.size(); if (n == 0) return 0; if (n == 1) return arr.get(0); int[] dp = new int[n]; dp[0] = arr.get(0); dp[1] = Math.max(arr.get(0), arr.get(1)); for (int i = 2; i < n; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr.get(i)); } return dp[n - 1]; } public static int maximizeSumGreedy(List<Integer> arr) { int include = 0, exclude = 0; for (int num : arr) { int new_include = exclude + num; exclude = Math.max(include, exclude); include = new_include; } return Math.max(include, exclude); } public static void main(String[] args) { List<Integer> inputArray = List.of(1, 2, 5, 4, 5); int resultDP = GFG(inputArray); int resultGreedy = GFG(inputArray); System.out.println("Using Dynamic Programming:"); System.out.println(resultDP); System.out.println("Using Greedy Algorithm:"); System.out.println(resultGreedy); }} |
Python3
# Python code for the above approach# Function to Calculate the maximum sum using dynamic programmingdef GFG(arr): n = len(arr) if n == 0: return 0 if n == 1: return arr[0] # Initialize an array dp = [0] * n dp[0] = arr[0] dp[1] = max(arr[0], arr[1]) # Traversing the loop and Calculating the maximum sum till index i for i in range(2, n): dp[i] = max(dp[i - 1], dp[i - 2] + arr[i]) return dp[n - 1]# Function to Calculate the maximum sum using the greedy approachdef maximizeSumGreedy(arr): # Initialize a variable to store the maximum sum including the current element include = 0 # # Initialize a variable to store the maximum sum excluding the current element exclude = 0 # Traverse the array and calculate the maximum sum using the greedy approach for num in arr: new_include = exclude + num exclude = max(include, exclude) include = new_include return max(include, exclude)# Driver Codeif __name__ == "__main__": inputArray = [1, 2, 5, 4, 5] resultDP = GFG(inputArray) resultGreedy = maximizeSumGreedy(inputArray) print("Using Dynamic Programming:") print(resultDP) print("Using Greedy Algorithm:") print(resultGreedy) # This code is contributed by Pushpesh Raj |
C#
using System;using System.Collections.Generic;class Program{ // Function to find the maximum sum of a subsequence // using Dynamic Programming static int GFG(List<int> arr) { int n = arr.Count; if (n == 0) return 0; if (n == 1) return arr[0]; List<int> dp = new List<int>(n); dp.Add(arr[0]); dp.Add(Math.Max(arr[0], arr[1])); for (int i = 2; i < n; i++) { dp.Add(Math.Max(dp[i - 1], dp[i - 2] + arr[i])); } return dp[n - 1]; } // Function to find the maximum sum of a subsequence // using Greedy Algorithm static int MaximizeSumGreedy(List<int> arr) { int include = 0, exclude = 0; foreach (int num in arr) { int new_include = exclude + num; exclude = Math.Max(include, exclude); include = new_include; } return Math.Max(include, exclude); } static void Main() { List<int> inputArray = new List<int> { 1, 2, 5, 4, 5 }; int resultDP = GFG(inputArray); int resultGreedy = MaximizeSumGreedy(inputArray); Console.WriteLine("Using Dynamic Programming:"); Console.WriteLine(resultDP); Console.WriteLine("Using Greedy Algorithm:"); Console.WriteLine(resultGreedy); }} |
Javascript
// Function to Calculate the maximum sum using dynamic programmingconst GFG = (arr) => { const n = arr.length; if (n === 0) { return 0; } if (n === 1) { return arr[0]; } // Initialize an array const dp = new Array(n).fill(0); dp[0] = arr[0]; dp[1] = Math.max(arr[0], arr[1]); // Traversing the loop and Calculating the maximum sum till index i for (let i = 2; i < n; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[i]); } return dp[n - 1];};// Function to Calculate the maximum sum using the greedy approachconst maximizeSumGreedy = (arr) => { // Initialize a variable to store the maximum sum including the current element let include = 0; // Initialize a variable to store the maximum sum excluding the current element let exclude = 0; // Traverse the array and calculate the maximum sum using the greedy approach for (let num of arr) { const new_include = exclude + num; exclude = Math.max(include, exclude); include = new_include; } return Math.max(include, exclude);};// Driver Codeconst inputArray = [1, 2, 5, 4, 5];const resultDP = GFG(inputArray);const resultGreedy = maximizeSumGreedy(inputArray);console.log("Using Dynamic Programming:");console.log(resultDP);console.log("Using Greedy Algorithm:");console.log(resultGreedy); |
output :
Using Dynamic Programming:
11
Using Greedy Algorithm:
11
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
