美团点评2017校园招聘编程题--取红包

题目：
圆桌上放了一圈红包形成环形，每个红包金额不同，围绕圆桌走一圈选择若干红包，规则是不能拿相邻的红包，请问拿到红包最多的总金额是多少？

输入：
红包个数N
N行数组表示N个红包

输出：
最多的总金额

样例输入：
2
1，2
1，3，4

样例输出：
2
4

代码：

import java.util.Scanner;

public class Test{
private static int func(int[] arr, int lo, int hi){
int include = 0, exclude = 0;
for(int j = lo; j <= hi; j++){
int i = include, e = exclude;
            include = e + arr[j];
            exclude = Math.max(i, e);
        }
return Math.max(include, exclude);
    }
public static int redBag(int[] arr){
if(arr.length == 1) return arr[0];
return Math.max(func(arr, 0, arr.length - 2), func(arr, 1, arr.length - 1));
    }
public static void main(String args[]){
        Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
for(int i = 0; i < n; i++){
                String s = in.next();
                String[] ss = s.split(",");
int[] arr = new int[ss.length];
for(int j = 0; j < ss.length; j++)
                    arr[j] = Integer.parseInt(ss[j]);
                System.out.println(redBag(arr));
            }
        }
    }
}

代码来源：https://discuss.leetcode.com/topic/14375/simple-ac-solution-in-java-in-o-n-with-explanation