2018 360Java在线笔试 算法题（1）

import java.util.Scanner;

public class Main {    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 2; i < n; i++) {
            if(getResult(i, arr)){
                System.out.println(i+1);
                break;
            }
            if(i==n-1)
                System.out.println(-1);
        }
    }
    /**
     * 判断前i个木棍是否能组成圈地
     * @param i
     * @param arr 
     * @return */
    private static boolean getResult(int i, int[] arr) {
        //考虑：什么时候不能组成圈地？
        //1.找出前i个木棍的最大值arr(max)
        int max = getMax(i, arr);//max为最大值的下标
        //2.将除最大值以外的前i个木棍长度加起来得到sum
        int sum = getTotal(max, arr, i);
        //3.若 a>=sum,则肯定组不成圈地，返回false
        if(arr[max] >= sum)
            return false;
        //4.否则返回true
        else
            return true;
    }
    private static int getTotal(int max, int[] arr, int i) {
        int sum = 0;
        for (int j = 0; j <= i; j++) {
            sum += arr[j];
        }
        return sum - arr[max];
    }
    private static int getMax(int i, int[] arr) {
        int max = 0;
        for (int j = 1; j <= i; j++) {
            if(arr[j]>arr[max])
                max = j;
        }
        return max;
    }
}