Problem#9 : Non-Adjacent Sum

All problems are from https://www.dailycodingproblem.com/

 

Solution Codes : https://github.com/Kusin/DailyCoding

Kusin/DailyCoding

Daily Coding Problem #9: Non-Adjacent Sum

Problem Description

Idea

Simple DP Problem.

 

We will set two different DP Table.

DP1 (i) : we seek 1st ~ ith elements. if we include ith element, what would be the max non-adjacent sum?

DP2 (i) : we seek 1st ~ ith elements. if we don't include ith element, what would be the max non-adjacent sum?

 

DP1(i) = DP2(i-1)+arr[i]

DP2(i) = max(DP1(i-1),DP2(i-1))

 

DP1[0] = arr[0]

DP2[0] = - INF

Implementation

Very Simple.