use std::cmp;

// Given a list of integers, write a function that returns the largest sum of
// non-adjacent numbers. Numbers can be 0 or negative. For example, [2, 4, 6, 2, 5]
// should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10,
// since we pick 5 and 5.
//
// Follow-up: Can you do this in O(N) time and constant space?

fn largest_non_adjacent(input: Vec<i32>) -> i32 {
    // 1. sum every other
    // 2. sum every other off by one.
    // 3. sum edges

    let mut sum_every_other = 0;
    let mut sum_every_other_off = 0;

    for x in 0..input.len() {
        if x % 2 == 0 {
            sum_every_other += input[x];
        }

        if x % 2 != 0 {
            sum_every_other_off += input[x];
        }
    }

    let edges = input[0] + input[input.len() - 1];
    let max = cmp::max(edges, cmp::max(sum_every_other, sum_every_other_off));

    return max;
}

#[cfg(test)]
mod test_largest {
    use super::*;

    #[test]
    fn example_cases() {
        assert_eq!(largest_non_adjacent(vec![2, 4, 6, 2, 5]), 13);
        assert_eq!(largest_non_adjacent(vec![5, 1, 1, 5]), 10);
    }

    #[test]
    fn custom_case() {
        assert_eq!(largest_non_adjacent(vec![2, 4, 2, 0, 2, 4, 2]), 8);
        assert_eq!(largest_non_adjacent(vec![10, 5, 5, 5, 10]), 25);
        assert_eq!(largest_non_adjacent(vec![-10, 0, -5, 0, 10]), 0);
    }
}

fn main() {}
