题解 | #不相邻取数#

//不相邻取数，取数个数不定
#include <stdio.h>
#include <malloc.h>

int main(){
    int n = 0;
    scanf("%d", &n);
    int* ans = (int*)malloc(sizeof(int)*n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &ans[i]);
    }
    int* temp = (int*)malloc(sizeof(int)*n);
    temp[0] = ans[0];
    temp[1] = ans[0] > ans[1] ? ans[0] : ans[1];
    for (int i = 2; i < n; i++) {
        temp[i] = ans[i] + temp[i - 2] > temp[i - 1] ? ans[i] + temp[i - 2] : temp[i - 1];
    }
    int max = temp[0];
    for (int i = 1; i < n; i++) {
        max = max > temp[i] ? max : temp[i];
    }
    printf("%d\n", max);
    return 0;
}