Dynamic Programming Samples

dynamic_programming.groovy

// max sum of non-consecutive numbers
def arr =  [3, 1, 4, 2, 5, 10 ]
//def arr =  [4,1,1,4,2,1]
//def arr =  [2,5,3,1,7]
def map = [:]

// non dynamic solution - brute force
for (int i = 0 ; i < arr.size() ; i++) {
    def sum = arr[i]
    def op = [arr[i]]
    for (int j = 0 ; j < arr.size() ; ) {
        if(i==j || i-1 ==j || i+1==j){ 
            j++
            continue;
        }
        sum +=arr[j]        
        op.add(arr[j])
        j+=2
    }
    map[sum] = op
    println map
}
// the highest key in Map will have the non-consecutive sequence with max sum