Problems? Solutions...
Problems
Apr 24th, 2009
Given an array, all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).
<?php
$arr = array( 5, 10, 2, 6, 4, 9, 3, 12, 1, 11 );
$sum = 0;
$sums = array();
for ( $i=0; $i<2; $i++ ) {
if ( isset( $arr[$i] ) ) {
$sums[] = $arr[$i];
add( $arr[$i], $i );
}
}
function add( $sum, $i ) {
global $sums;
global $arr;
if ( isset( $arr[$i+2] ) ) {
$plusSecond = $sum + $arr[$i+2];
$sums[] = $plusSecond;
add( $plusSecond, $i+2 );
}
if ( isset( $arr[$i+3] ) ) {
$plusThird = $sum + $arr[$i+3];
$sums[] = $plusThird;
add( $plusThird, $i+3 );
}
}
echo "Max Sum: " . max( $sums ) . "\n";
?>
Completely Academic. This was a question on a skills test. There are much more involved ways to do it. Probably not exremely memory-safe for very large arrays of integers, but works well and is very concise.