text: GFG App
  Open App
  Browser
  Continue
  
  # Minimize sum of max sized Subsequence such that no two elements are adjacent
  
  Given an array arr[] of positive numbers, the task is to find the minimum sum of a subsequence of maximum possible elements with the constraint that no two numbers in the sequence are adjacent.
  
  Examples:
  
  Input: arr[]={1, 7, 3, 2}
  Output: 3
  Explanation: Pick the subsequence {1, 2}.
  The sum is 3 and no two elements are adjacent.
  This is the least possible sum.
  
  Input: arr[]={1, 8, 4, 10, 6}
  Output: 11
  Explanation: Pick the subsequence {1, 4, 6}.
  The sum is 11 and no two elements are adjacent.
  This is the least possible sum.
  
  Input: arr[]={2, 0, 11, 2, 0, 2}
  Output: 4
  Explanation: Pick the subsequence {0, 2, 2}.
  The sum is 4 and no two elements are adjacent.
  This is the least possible sum.
  
  Approach: To solve the problem follow the below observations:
  
  There are two different cases:
  
  • Array size is Odd – the only choice is to pick the even indexed elements(Zero – Based Indexing).
  • Array size is Even – The subsequence size will be N/2. It can be in three possible ways
  • All the even indexed elements.
  • All the odd indexed elements.
  • Even indexed elements till i and odd indexed elements starting from i+3
  • The minimum among these 3 will be the answer.
  
  Follow the steps to solve the problem:
  
  • If the size of arr[] is Odd, the sum of all the even indexed elements is the answer.
  • For Size of arr to Even, store the sum of all the even indices into a variable.
  • Iterating from the end by adding the odd index elements and removing the even indexed elements from the end.
  • Update the minimum answer in each index.
  • After the iteration is over, return the minimum value as the answer.
  
  Below is the implementation of the above approach.
  
  ## C++
  
  ```// C++ code for the above approach:
  
  #include <bits/stdc++.h>
  using namespace std;
  
  // Function to find the minimum sum
  int FindMinSum(vector<int>& vec, int n)
  {
  int sum = 0;
  for (int i = 0; i < n; i += 2) {
  
  // Sum of all the even indices
  sum += vec[i];
  }
  if (n % 2 != 0)
  return sum;
  int ans = sum;
  for (int i = n - 1; i > 0; i -= 2) {
  
  // Removing the even index and
  sum = sum - vec[i - 1] + vec[i];
  
  // Checking for the minimum sum
  ans = min(sum, ans);
  }
  
  // Return the minimum sum
  return ans;
  }
  
  // Driver Code
  int main()
  {
  
  // Creating the array
  vector<int> arr = { 2, 0, 11, 2, 0, 2 };
  int N = vec.size();
  
  // Function call
  cout << FindMinSum(arr, N) << endl;
  
  return 0;
  }```
  
  ## C
  
  ```#include <stdio.h>
  
  int FindMinSum(int arr[], int n)
  {
  int sum = 0;
  for (int i = 0; i < n; i += 2) {
  // sum of all the odd indexes
  sum += arr[i];
  }
  if (n % 2 == 1)
  return sum;
  int ans = sum;
  for (int i = n - 1; i > 0; i -= 2) {
  // removing the odd index and addinig the even index
  sum = sum - arr[i - 1] + arr[i];
  // checking for the minimum sum
  if (sum < ans)
  ans = sum;
  }
  
  // Return the minimum sum
  return ans;
  }
  // Driver Code
  int main()
  {
  // Creating the array
  int arr[] = { 2, 0, 11, 2, 0, 2 };
  int n = *(&arr + 1) - arr;
  
  // Function call
  
  return 0;
  }```
  
  ## Java
  
  ```import java.io.*;
  import java.util.*;
  
  public class GFG {
  
  static int solve(int vec[], int n)
  {
  int sum = 0;
  if (n % 2 != 0) {
  for (int i = 0; i < n; i = i + 2) {
  // sum of all the odd indexes
  sum = sum + vec[i];
  }
  return sum;
  }
  else {
  int ans = sum;
  for (int i = n - 1; i > 0; i -= 2) {
  // removing the odd index and addinig the
  // even index
  ans = ans - vec[i - 1] + vec[i];
  // checking for the minimum sum
  ans = Math.min(ans, sum);
  }
  // Return the minimum sum
  return ans;
  }
  }
  public static void main(String args[])
  throws IOException
  {
  // Creating the array
  int vec[] = { 2, 1, 2 };
  
  int n = vec.length;
  
  // Function call
  System.out.println(solve(vec, n));
  }
  }```
  
  ## Python
  
  ```# Python code to implement the approach
  def FindMinSum(list, n):
  sum = 0
  for i in range(0, n, 2):
  # sum of all the odd indexes
  sum = sum + list[i]
  if n % 2 == 1:
  return sum
  ans = sum
  for i in range(n-1, 0, -2):
  # removing the odd index and addinig the even index
  sum = sum - list[i-1] + list[i]
  # checking for the minimum sum
  ans = min(sum, ans)
  # Return the minimum sum
  return ans
  
  # Driver Code
  # Creating the list
  list = [2, 0, 11, 2, 0, 2]
  n = 6
  # Function call
  k = FindMinSum(list, n)
  print(k)
  ```
  
  ## C#
  
  ```// C# code for the above approach:
  using System;
  
  public class GFG {
  static int solve(int[] vec, int n)
  {
  int sum = 0;
  if (n % 2 != 0) {
  for (int i = 0; i < n; i = i + 2)
  {
  
  // sum of all the odd indexes
  sum = sum + vec[i];
  }
  return sum;
  }
  else {
  int ans = sum;
  for (int i = n - 1; i > 0; i -= 2)
  {
  
  // removing the odd index and addinig the
  // even index
  ans = ans - vec[i - 1] + vec[i];
  
  // checking for the minimum sum
  ans = Math.Min(ans, sum);
  }
  
  // Return the minimum sum
  return ans;
  }
  }
  
  // Driver Code
  static public void Main()
  {
  // Creating the array
  int[] vec = { 2, 1, 2 };
  
  int n = vec.Length;
  
  // Function call
  Console.WriteLine(solve(vec, n));
  }
  }
  
  // This code is contributed by Rohit Pradhan```
  
  ## Javascript
  
  ```    <script>
  // JavaScript code for the above approach:
  
  // Function to find the minimum sum
  const FindMinSum = (vec, n) => {
  let sum = 0;
  for (let i = 0; i < n; i += 2) {
  
  // Sum of all the even indices
  sum += vec[i];
  }
  if (n % 2 != 0)
  return sum;
  let ans = sum;
  for (let i = n - 1; i > 0; i -= 2) {
  
  // Removing the even index and
  sum = sum - vec[i - 1] + vec[i];
  
  // Checking for the minimum sum
  ans = Math.min(sum, ans);
  }
  
  // Return the minimum sum
  return ans;
  }
  
  // Driver Code
  
  // Creating the array
  let arr = [2, 0, 11, 2, 0, 2];
  let N = arr.length;
  
  // Function call
  document.write(FindMinSum(arr, N));
  
  // This code is contributed by rakeshsahni
  
  </script>```
  Output
  
  `4`
  
  Time Complexity: O(N)
  Auxiliary Space: O(1)
  
  My Personal Notes arrow_drop_up
metadata: {"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}