4041424344454647484950515253545556

package main

import (
	"fmt"
)

// Helper function to get maximum of two numbers
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// Function to calculate the maximum sum of non-adjacent elements
func nonAdjacent(nums []int) int {
	n := len(nums)

	// Handle base cases
	if n == 0 {
		return 0
	}
	if n == 1 {
		return nums[0]
	}

	// Initialize dp array
	dp := make([]int, n)

	// Base case
	dp[0] = nums[0]

	// Iterate through the elements of the array
	for i := 1; i < n; i++ {
		// Calculate maximum value by either picking or not picking the current element
		pick := nums[i]
		if i > 1 {
			pick += dp[i-2]
		}
		nonPick := dp[i-1]

		// Store the maximum value in dp array
		dp[i] = max(pick, nonPick)
	}

	// The last element of dp array will contain the maximum sum
	return dp[n-1]
}

func main() {
	arr := []int{2, 1, 4, 9}

	// Call the solve function and print the result
	fmt.Println("Maximum sum of non-adjacent elements:", nonAdjacent(arr))
}

Complexity Analysis:

Time Complexity: O(N), where N is the given size of array. As each element of the array is processed exactly once in a single pass.

Space Complexity:O(N), as an additional dp array is used, which stores results for each element of the array.1f:T3415,

If we do some observation, we find that the values required at every iteration for dp[i] are dp[i-1] and dp[i-2]. we see that for any i, we do need only the last two values in the array. So is there is no need to maintain a whole array for it.

Let us call dp[i-1] as prev and dp[i-2] as prev2. Now understand the following illustration:

Each iteration cur_i and prev become the next iteration’s prev and prev2 respectively. Therefore after calculating cur_i, if we update prev and prev2 according to the next step, we will always get the answer.

After the iterative loop has ended we can simply return prev as our answer. As at the end of the loop prev will contain curr_i, the maximum sum.

1234567891011121314151617181920212223242526272829303132333435363738394041<