House Robber (Max Non-Adjacent Sum)

📌 Definition:

📖 Detailed Explanation:

At each element you either skip it (keep the best-so-far) or take it plus the best from two positions back: curr = max(prev, prevPrev + x). Track just two rolling values for O(n) time, O(1) space. Greedily taking the largest values can violate the adjacency rule.

💻 Solutions:

• Java
• JavaScript
• Python

public static int rob(int[] a) {
    int prev = 0, curr = 0;
    for (int x : a) {
        int temp = Math.max(curr, prev + x);
        prev = curr;
        curr = temp;
    }
    return curr;
}

function rob(a) {
  let prev = 0, curr = 0;
  for (const x of a) {
    const temp = Math.max(curr, prev + x);
    prev = curr;
    curr = temp;
  }
  return curr;
}

def rob(a):
    prev = curr = 0
    for x in a:
        prev, curr = curr, max(curr, prev + x)
    return curr

🔑 Key Points:

• take vs skip: curr = max(prev, prevPrev + x)
• Two rolling variables — O(1) space
• Greedy on largest values is wrong
• O(n) time

🌍 Real-World Example: