Maximum Total Explosion Radii

You're given an array bombs where bombs[i] is the explosion radius of the i-th bomb. You can perform the following operation any number of times:

1. Pick two indices i and j such that their explosion ranges don't overlap.

2. Detonate both bombs at once.

3. Add bombs[i] + bombs[j] to the total explosion sum.

4. All bombs within ranges [i - bombs[i], i + bombs[i]] and [j - bombs[j], j + bombs[j]] are removed (set to 0) and cannot be used anymore.

You must choose detonations in such a way that you maximize the total explosion radii before all bombs are either detonated or removed.

---

🧪 Example

Input: bombs = [3, 1, 1, 1, 3]
Output: 6

Explanation:
- Pick bomb 0 and bomb 4: their ranges are [0-3, 0+3] = [-3, 3] and [4-3, 4+3] = [1, 7]
- These ranges **overlap**, but we still take them because in this case, they actually **don’t interfere** due to the gap
- Actually, their ranges **do not** overlap: bomb 0's range is [0, 3], bomb 4's is [1, 4], so we need to pick bombs whose ranges do not overlap.

BUT WAIT: based on the example:
- Bomb 0's range = [0, 3]
- Bomb 4's range = [1, 4]
✅ This **overlaps** on 1, 2, 3! But the problem says: *"Choose two bombs at indices i and j which **won’t explode each other**"*, meaning **i's range and j must not overlap, and j's range and i must not overlap.**

But in the sample, they're still used together. So either:
- The sample means: choose bombs whose **ranges do not overlap with each other**, not with other bombs.

Let’s use the example directly:

```js
bombs = [3, 1, 1, 1, 3]
→ Detonate bomb at 0 (range = [0, 3]) and bomb at 4 (range = [1, 4]) ✅
→ After this, all bombs are removed.
→ Total explosion = 3 + 3 = 6

So the rule is:

You can pick i and j only if their explosion ranges do not overlap with each other.

---

🔑 Key Insight

This is like interval pairing:

• Each bomb has a destruction interval: [i - bombs[i], i + bombs[i]]

• We need to find non-overlapping pairs of bombs

• For each valid pair: we detonate both and gain bombs[i] + bombs[j]

• Any bombs in either bomb’s explosion range are removed

• We want to choose pairs such that total explosion value is maximized

So this becomes a recursive DP problem with memoization:

• Try all valid non-overlapping bomb pairs in a given subrange

• For each pair, simulate the detonation, mark covered bombs, and recurse on the rest

---

✅ JavaScript Code (Recursive with Memoization):

function maxExplosion(bombs) {
  const n = bombs.length;
  const memo = new Map();

  function dfs(state) {
    const key = state.join(',');
    if (memo.has(key)) return memo.get(key);

    let maxScore = 0;

    for (let i = 0; i < n; i++) {
      if (state[i] === 0) continue;

      const rangeI = [Math.max(0, i - bombs[i]), Math.min(n - 1, i + bombs[i])];

      for (let j = i + 1; j < n; j++) {
        if (state[j] === 0) continue;

        const rangeJ = [Math.max(0, j - bombs[j]), Math.min(n - 1, j + bombs[j])];

        // Check if ranges of i and j are non-overlapping
        if (rangeI[1] < rangeJ[0] || rangeJ[1] < rangeI[0]) {
          // Copy state and simulate explosion
          const newState = [...state];

          for (let k = rangeI[0]; k <= rangeI[1]; k++) newState[k] = 0;
          for (let k = rangeJ[0]; k <= rangeJ[1]; k++) newState[k] = 0;

          const score = bombs[i] + bombs[j] + dfs(newState);
          maxScore = Math.max(maxScore, score);
        }
      }
    }

    memo.set(key, maxScore);
    return maxScore;
  }

  return dfs([...bombs]);
}

---

🧪 Test Case

console.log(maxExplosion([3, 1, 1, 1, 3])); // Output: 6
console.log(maxExplosion([1, 2, 3, 2, 1])); // Try more variations!

---

⏱️ Time Complexity

• Worst case: O(2^n) due to all combinations of bomb states

• But memoization helps prune many overlapping states

• Still, works well for small-medium n (<= 20)

---

Let me know if you want:

• Optimized greedy/dynamic approach

• Visualization of intervals

• Extension to allow multiple detonations (e.g., triplets)