Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

    • Robbing houses

    You are planning to rob houses on a street. There are n houses and you know the amount of money you can rob from each of those. The alarm system automatically contacts the police if two adjacent houses are robbed on the same night.
    What would be the maximum possible amount you could get during one night without getting caught?

    Input

    The first line of the input contains a single integer n (1 ≤ n ≤ ).
    The next line contains n space-separated integers (1 ≤ ≤ ) the amount you can rob from each house.

    Output

    The program should print the maximum possible amount you could get without getting caught.

    Examples

    Input
    Output
    4 1 2 5 1
    6
    5 3 17 12 3 7
    24

    Explanation

    1. 1 + 5
    1. 17 + 7 (skip some houses in between)
     

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue