Given an array arr of integers of size N, the task is to find a subsequence in which upon reversing the order, the maximum sum subarray can be obtained.
Examples:
Input: arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}
Output: [-2 -3 1 5]
Explanation : After selecting subsequence -2 -3 1 5 and reverse it elements, modified array will be {5, 1, 4, -1, -2, -3, -2, -3} and thus the maximum contagious sum i.e. 5 + 1 + 4 = 10Input: arr[] = {2, -6, -12, 7, -13, 9, -14}
Output: [-6 -12 7 9]
Explanation: After selecting the above subsequence modified array will be {2, 9, 7, -12, -13, -6, -14} and thus the maximum contagious sum i.e. is 2 + 9 + 7 = 18
Approach: The idea is simple we have to modify the array such that all positive elements comes together, so we have to find the subsequence such that all positive elements come together when we reverse the subsequence.
- Let suppose there are ” p ” non- negative elements in the array. Divide the array into two parts: first p elements and the remaining elements .
- let ” px ” be non-negative elements in first part of array. so the negative elements in the first part will be:
(size of first part of array – number of non-negative elements) = p – px
- Also number of non-negative elements in second part of array is
(total non-negative elements – non-negative elements in first part of array) = p – px
- So we have to select negative elements p- px elements from first part and p-px non-negative elements from the second part of array.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;vector<int> findSubsequce(int arr[], int n){ int p = 0; for (int i = 0; i < n; i++) { if (arr[i] >= 0) p++; } vector<int> res; // store negative elements present // from 0 to p-1 index for (int i = 0; i < p; i++) { if (arr[i] < 0) res.push_back(arr[i]); } // store non-negative elements // present from p to n index for (int i = p; i < n; i++) { if (arr[i] >= 0) res.push_back(arr[i]); } return res;}// Driver codeint main(){ int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = sizeof(arr) / sizeof(arr[0]); vector<int> res = findSubsequce(arr, n); for (int i = 0; i < res.size(); i++) { cout << res[i] << " "; }} |
Java
// Java code to implement the above approachimport java.io.*;import java.util.*;class GFG { public static ArrayList<Integer> findSubsequence(int arr[], int n) { int p = 0; for (int i = 0; i < n; i++) { if (arr[i] >= 0) p++; } ArrayList<Integer> res = new ArrayList<Integer>(); // store negative elements // present from 0 to p-1 index for (int i = 0; i < p; i++) { if (arr[i] < 0) res.add(arr[i]); } // store non-negative elements // present from p to n index for (int i = p; i < n; i++) { if (arr[i] >= 0) res.add(arr[i]); } return res; } // Driver code public static void main(String[] args) { int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = arr.length; ArrayList<Integer> res = findSubsequence(arr, n); for (int i = 0; i < res.size(); i++) { System.out.print(res.get(i) + " "); } }} |
Python3
# Python 3 code to implement the above approachdef findSubsequce(arr, n): p = 0 for i in range(n): if (arr[i] >= 0): p += 1 res = [] # store negative elements present # from 0 to p-1 index for i in range(p): if (arr[i] < 0): res.append(arr[i]) # store non-negative elements # present from p to n index for i in range(p, n): if (arr[i] >= 0): res.append(arr[i]) return res# Driver codeif __name__ == "__main__": arr = [-2, -3, 4, -1, -2, 1, 5, -3] n = len(arr) res = findSubsequce(arr, n) for i in range(len(res)): print(res[i], end=" ") # This code is contributed by ukasp. |
C#
// C# code to implement the above approachusing System;using System.Collections;public class GFG{ public static ArrayList findSubsequence(int[] arr, int n) { int p = 0; for (int i = 0; i < n; i++) { if (arr[i] >= 0) p++; } var res = new ArrayList(); // store negative elements // present from 0 to p-1 index for (int i = 0; i < p; i++) { if (arr[i] < 0) res.Add(arr[i]); } // store non-negative elements // present from p to n index for (int i = p; i < n; i++) { if (arr[i] >= 0) res.Add(arr[i]); } return res; } // Driver code static public void Main (){ int[] arr = { -2, -3, 4, -1, -2, 1, 5, -3 }; int n = arr.Length; ArrayList res = findSubsequence(arr, n); for (int i = 0; i < res.Count; i++) { Console.Write(res[i] + " "); } }}// This code is contributed by hrithikgarg03188. |
Javascript
<script> // JavaScript code for the above approachfunction findSubsequce(arr, n){ let p = 0; for (let i = 0; i < n; i++) { if (arr[i] >= 0) p++; } let res =[]; // store negative elements present // from 0 to p-1 index for (let i = 0; i < p; i++) { if (arr[i] < 0) res.push(arr[i]); } // store non-negative elements // present from p to n index for (let i = p; i < n; i++) { if (arr[i] >= 0) res.push(arr[i]); } return res;}// Driver code let arr = [-2, -3, 4, -1, -2, 1, 5, -3] let n = arr.length; let res = findSubsequce(arr, n); for (let i = 0; i < res.length; i++) { document.write(res[i]+ " ") } // This code is contributed by Potta Lokesh </script> |
-2 -3 1 5
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Topic: Subarrays, Subsequences, and Subsets in Array
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
