# 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

````js
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):

```javascript
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

```javascript
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` (&lt;= 20)
    

---

Let me know if you want:

* Optimized greedy/dynamic approach
    
* Visualization of intervals
    
* Extension to allow multiple detonations (e.g., triplets)