Tuesday, 27 August 2013

Algorithm for selecting the largest sum for adjacent elements

Algorithm for selecting the largest sum for adjacent elements

I've been playing around a bit with the algorithms for getting the largest
sum with no two adjacent elements in an array but I was thinking:
If we have an array with n elements and we want to find the largest sum so
that 3 elements never touch. That's to say if we have the array a = [2, 5,
3, 7, 8, 1] we can pick 2 and 5 but not 2, 5 and 3 because then we have 3
in a row. The larget sum with these rules for this array would be: 22 (2
and 5, 7 and 8. 2+5+7+8=22)
I'm not sure how I would implement this, any ideas?
Edit:
I've only come so far as to think about what might be good to do:
Let's just stick to the same array:
int[] a = {2, 5, 3, 7, 8, 1};
int{} b = new int[n}; //an array to store results in
int n = a.length;
// base case
b[1] = a[1];
// go through each element:
for(int i = 1; i < n; i++)
{
/* find each possible way of going to the next element
use Math.max to take the "better" option to store in the array b*/
}
return b[n]; // return the last (biggest) element.
This is just a thought I got in my head, hasn't reached longer than this.

No comments:

Post a Comment