Question

write a program to find the maximum possible sum such that no two chosen numbers are adjacent either vertically, horizontally, or diagonally. code in java

Answer 1

Solution

Source code

Main.java

class Main
{
  
int maximumsum(int array[], int n)
{
int include = array[0];
int exclude = 0;
int exclude_new;
int i;
  
for (i = 1; i < n; i++)
{

exclude_new = (include > exclude) ? include : exclude;
  

include = exclude + array[i];
exclude = exclude_new;
}
  
  
return ((include > exclude) ? include : exclude);
}
  
  
public static void main(String[] args)
{
Main sum = new Main();
int array[] = new int[]{1,21,3};
System.out.println(sum.maximumsum(array, array.length));
}
}

Screenshot

Output

Explanation

array[] = {5, 5, 10, 40, 50, 35}

include = 5
exclude = 0

For i = 1 (current element is 5)
include = (exclude + array[i]) = 5
exclude = max(5, 0) = 5

For i = 2 (current element is 10)
include = (exclude + array[i]) = 15
exclude = max(5, 5) = 5

For i = 3 (current element is 40)
include = (exclude + array[i]) = 45
exclude = max(5, 15) = 15

For i = 4 (current element is 50)
include = (exclude + array[i]) = 65
exclude = max(45, 15) = 45

For i = 5 (current element is 35)
include = (exclude + array[i]) = 80
exclude = max(65, 45) = 65

And 35 is the last element. So, answer is max(include, exclude) = 80