Problem Link - Final Solution in Dynamic programming

### Problem Statement:

Given N integers, you have to pick a valid subset with the largest sum from these integers.

A valid subset is a subset in which no two adjacent elements are picked.

### Approach:

- We will use a
**DP**array where dp[i] represents the maximum sum of any valid subset that can be formed from the first i integers, respecting the rule that no two adjacent elements are picked. - For each integer A[i], we have two options:
- Include: If we include A[i] in the subset, we cannot include A[i−1], so the total sum will be dp[i−2]+A[i];
- Exclude: If we exclude A[i], then the total sum will simply be dp[i−1].

- Therefore, the recurrence relation is dp[i]=max(dp[i−1],dp[i−2]+A[i]). The idea is to make a choice at each position based on the previous computations.
- The first element’s maximum sum is either 0 (if we don’t select it) or the element itself.
- For the second element, we can either pick just the second element or stick with the first one.

### Complexity:

**Time Complexity:**`O(N)`

Traversing the array once for calculating dp array`O(N)`

and calculating the maximum value for the answer`O(N)`

.`2*O(N)->O(N)`

**Space Complexity:**`O(N)`

Assigning the dp array with`N+1`

.