algorithms/maxSumWithTwist.js at master · bpnetguy/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/*
 * Given a array with +ve and -ve integer , find the maximum sum such that you are not allowed to skip 2 contiguous elements ( i.e you have to select atleast one of them to move forward).
 * eg :-
 * 10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3
 * Output : 10+20+30-10+40-1 = 89
 */
var data = [10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3];
function max(array) {
    var i = array[0];
    array.forEach(function(val) {
	if(val > i)
		i = val;
    });
    return i;
}
function maxSum(i, data, canSkip) {
var data = [10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3];
   var len = data.length  - i;
   if( len === 1) {
       if(canSkip && data[i] < 0) {
           return 0;
       } else {
           return data[i];
var data = [10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3];
       }
   } else if(len <1) {
      return 0;
   }
   var skippedI =  maxSum(i + 1, data, false);
   var notSkippedISkippedJ =  maxSum(i + 1, data, true) + data[i];
var data = [10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3];
   var notSkippedINotSkippedJ =  maxSum(i + 2, data, false) + data[i] + (data[i+1] || 0);
   if(canSkip) {
	return max([skippedI, notSkippedISkippedJ, notSkippedINotSkippedJ]);
   } else {
	return max([notSkippedISkippedJ, notSkippedINotSkippedJ]);
   }
var data = [10 , 20 , 30, -10 , -50 , 40 , -50, -1, -3];
function max(array) {
    var i = array[0];
    array.forEach(function(val) {
        if(val > i)
                i = val;
    });
    return i;
}
function maxSum(i, data, canSkip) {
   var len = data.length  - i;
   if( len === 1) {
       if(canSkip && data[i] < 0) {
           return 0;
       } else {
           return data[i];
       }
   } else if(len <1) {
      return 0;
   }
   var skippedI =  maxSum(i + 1, data, false);
   var notSkippedISkippedJ =  maxSum(i + 1, data, true) + data[i];
   var notSkippedINotSkippedJ =  maxSum(i + 2, data, true) + data[i] + (data[i+1] || 0);
   if(canSkip) {
        return max([skippedI, notSkippedISkippedJ, notSkippedINotSkippedJ]);
   } else {
        return max([notSkippedISkippedJ, notSkippedINotSkippedJ]);
   }
}

console.log(maxSum(0, data, true));