C Exercises: Return maximum sum such that no two elements are adjacent

Last update on March 18 2025 13:21:09 (UTC/GMT +8 hours)

68. Maximum Sum of Non-adjacent Elements

Write a program in C to return the maximum sum such that no two elements are adjacent.

Expected Output :
The given array is : 1 3 5 9 7 10 1 10 100
The maximum sum from the array such that no two elements are adjacent is: 122

The objective is to write a C program that finds the maximum sum of elements in an array such that no two selected elements are adjacent. The program should iterate through the array and use dynamic programming or a similar approach to ensure the highest possible sum is calculated while maintaining the non-adjacency condition.

Visual Presentation:

C Exercises: Return maximum sum such that no two elements are adjacent.

Sample Solution:

C Code:

#include <stdio.h>

// Function to find the maximum sum of elements in an array such that no two elements are adjacent
int maxSumSubseq(int arr1[], int n) {
int incl = arr1[0];  // Initialize incl as the first element of the array
int excl = 0;         // Initialize excl as 0, representing no elements chosen initially
int excl_new;         // Temporary variable to store the updated value of excl
int i;

for (i = 1; i < n; i++) {
        // Store the larger of incl and excl in excl_new
        excl_new = (incl > excl) ?incl : excl;

        // Update incl to the sum of the current element and excl
incl = excl + arr1[i];

        // Update excl to the larger of previous excl and excl_new (which was either incl or excl)
excl = excl_new;
    }

    // Return the maximum of incl and excl as the final result
return ((incl > excl) ? incl : excl);
}

int main() {
int arr1[] = {1, 3, 5, 9, 7, 10, 1, 10, 100};
int n = sizeof(arr1) / sizeof(arr1[0]);
int i;

    // Printing the original array
printf("The given array is :  ");
for (i = 0; i < n; i++) {
printf("%d  ", arr1[i]);
    } 
printf("\n");

    // Finding and printing the maximum sum of non-adjacent elements in the array
printf("The maximum sum from the array such that no two elements are adjacent is: %d \n", maxSumSubseq(arr1, n));
return 0;
}

Output:

The given array is :  1  3  5  9  7  10  1  10  100  
The maximum sum from the array such that no two elements are adjacent is: 122

Flowchart:/p>

For more Practice: Solve these Related Problems:

Write a C program to calculate the maximum sum of non-adjacent elements using dynamic programming.
Write a C program to compute the maximum sum of non-adjacent elements recursively with memoization.
Write a C program to find the maximum non-adjacent sum and then output the selected elements.
Write a C program to determine the maximum sum from non-adjacent elements by simulating both include and exclude cases.

C Programming Code Editor:

Previous: Write a program in C to search an element in a row wise and column wise sorted matrix.
Next: Write a program in C to find out the maximum difference between any two elements such that larger element appears after the smaller number.