import java.util.Scanner; import java.util.InputMismatchException; public class Sushi{ public static void main(String[] args){ Scanner scanner = new Scanner(System.in); try{ //寿司の数を入力して数値が条件内かチェック int N = scanner.nextInt(); if(N < 1 || N > 1000){ System.out.println("Nは1以上1000以下で入力してください"); System.exit(0); } //食べた寿司の美味しさを数える長さNのカウント配列を定義 int[] Count = new int[N]; //与えられた個数の美味しさ数をint配列に順番に入れていく int[] Delicious = new int[N]; for(int i = 0 ; i < N ; i++){ Delicious[i] = scanner.nextInt(); if(Delicious[i] < 1 || Delicious[i] > 100){ System.out.println("美味しさは1以上100以下で入力してください"); System.exit(0); } } //もしもNが1だった場合その値が答えになるので先に条件分岐 if(N > 1){ Count[1] = Math.max(Delicious[0],Delicious[1]); }else{ System.out.println(Delicious[0]); System.exit(0); } //Nが2以上の場合に一番美味しさ数が多くなる組み合わせを動的計画法で抽出 for(int j = 2 ; j < N ; j++){ if(Count[0] == 0){ Count[0] = Delicious[0]; } Count[j] = Math.max(Count[j - 1],Count[j - 2] + Delicious[j]); } //Count[N - 1]が取りうる最大の美味しさ数の合計になっているのでプリントする System.out.println(Count[N - 1]); }catch(InputMismatchException e){ System.out.println("数字で入力してください"); }catch(Exception E){ System.out.println("予期せぬエラーです"); } } }