Even Odd Sum Equilibrium — Problem Statement & Solution Guide

#include <bits/stdc++.h>
using namespace std;

int evenOddSumEquilibrium(const vector<int>& values) {
    // dpEven[diff] = maximum sum of elements placed at even positions so far
    // when the next element to be placed will be at an even index.
    // dpOdd[diff]  = same, but the next index is odd.
    unordered_map<long long, long long> dpEven, dpOdd;
    dpEven[0] = 0; // empty subsequence, next position is even, diff = 0

    for (int v : values) {
        unordered_map<long long, long long> nextEven = dpEven;
        unordered_map<long long, long long> nextOdd  = dpOdd;
        // Take v when next position is even -> it becomes an even-indexed element
        for (auto &p : dpEven) {
            long long diff = p.first;
            long long sumEven = p.second;
            long long newDiff = diff + v; // E - O increases by v
            long long newSumEven = sumEven + v; // v contributes to even sum
            auto it = nextOdd.find(newDiff);
            if (it == nextOdd.end() || it->second < newSumEven) {
                nextOdd[newDiff] = newSumEven;
            }
        }
        // Take v when next position is odd -> it becomes an odd-indexed element
        for (auto &p : dpOdd) {
            long long diff = p.first;
            long long sumEven = p.second; // unchanged, v goes to odd side
            long long newDiff = diff - v; // E - O decreases by v
            auto it = nextEven.find(newDiff);
            if (it == nextEven.end() || it->second < sumEven) {
                nextEven[newDiff] = sumEven;
            }
        }
        dpEven.swap(nextEven);
        dpOdd.swap(nextOdd);
    }
    long long ans = 0; // empty subsequence gives E = 0
    if (dpEven.count(0)) ans = max(ans, dpEven[0]);
    if (dpOdd.count(0))  ans = max(ans, dpOdd[0]);
    return static_cast<int>(ans);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin >> n)) return 0;
    vector<int> values(n);
    for (int i = 0; i < n; ++i) cin >> values[i];
    cout << evenOddSumEquilibrium(values) << "\n";
    return 0;
}

import java.util.*;

public class Main {
    // Returns the maximum possible sum E such that a subsequence exists where
    // the sum of elements at even positions equals the sum at odd positions (E = O).
    public static int evenOddSumEquilibrium(int[] values) {
        Map<Long, Long> dpEven = new HashMap<>(); // diff -> max sumEven, next index even
        Map<Long, Long> dpOdd = new HashMap<>();  // diff -> max sumEven, next index odd
        dpEven.put(0L, 0L);
        for (int v : values) {
            Map<Long, Long> nextEven = new HashMap<>(dpEven);
            Map<Long, Long> nextOdd = new HashMap<>(dpOdd);
            // place v at even position
            for (Map.Entry<Long, Long> e : dpEven.entrySet()) {
                long diff = e.getKey();
                long sumEven = e.getValue();
                long newDiff = diff + v;
                long newSumEven = sumEven + v;
                nextOdd.merge(newDiff, newSumEven, Math::max);
            }
            // place v at odd position
            for (Map.Entry<Long, Long> e : dpOdd.entrySet()) {
                long diff = e.getKey();
                long sumEven = e.getValue(); // unchanged
                long newDiff = diff - v;
                nextEven.merge(newDiff, sumEven, Math::max);
            }
            dpEven = nextEven;
            dpOdd = nextOdd;
        }
        long ans = 0;
        if (dpEven.containsKey(0L)) ans = Math.max(ans, dpEven.get(0L));
        if (dpOdd.containsKey(0L))  ans = Math.max(ans, dpOdd.get(0L));
        return (int) ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] values = new int[n];
        for (int i = 0; i < n; ++i) values[i] = sc.nextInt();
        System.out.println(evenOddSumEquilibrium(values));
    }
}

def even_odd_sum_equilibrium(values):
    """Return the maximum possible sum E such that a subsequence exists where
    the sum of elements at even positions equals the sum at odd positions (E = O)."""
    dp_even = {0: 0}  # diff -> max sum_even, next index is even
    dp_odd = {}       # diff -> max sum_even, next index is odd
    for v in values:
        next_even = dp_even.copy()
        next_odd = dp_odd.copy()
        # place v at an even position
        for diff, sum_even in dp_even.items():
            new_diff = diff + v
            new_sum_even = sum_even + v
            if new_diff not in next_odd or next_odd[new_diff] < new_sum_even:
                next_odd[new_diff] = new_sum_even
        # place v at an odd position
        for diff, sum_even in dp_odd.items():
            new_diff = diff - v
            if new_diff not in next_even or next_even[new_diff] < sum_even:
                next_even[new_diff] = sum_even
        dp_even, dp_odd = next_even, next_odd
    ans = 0
    if 0 in dp_even:
        ans = max(ans, dp_even[0])
    if 0 in dp_odd:
        ans = max(ans, dp_odd[0])
    return ans

if __name__ == "__main__":
    n = int(input())
    values = list(map(int, input().split()))
    print(even_odd_sum_equilibrium(values))

function evenOddSumEquilibrium(values) {
    // dpEven and dpOdd map diff -> max sumEven
    const dpEven = new Map(); // next index is even
    const dpOdd = new Map();  // next index is odd
    dpEven.set(0, 0);
    for (const v of values) {
        const nextEven = new Map(dpEven);
        const nextOdd = new Map(dpOdd);
        // take v at even position
        for (const [diff, sumEven] of dpEven.entries()) {
            const newDiff = diff + v;
            const newSumEven = sumEven + v;
            if (!nextOdd.has(newDiff) || nextOdd.get(newDiff) < newSumEven) {
                nextOdd.set(newDiff, newSumEven);
            }
        }
        // take v at odd position
        for (const [diff, sumEven] of dpOdd.entries()) {
            const newDiff = diff - v;
            const newSumEven = sumEven; // unchanged
            if (!nextEven.has(newDiff) || nextEven.get(newDiff) < newSumEven) {
                nextEven.set(newDiff, newSumEven);
            }
        }
        dpEven.clear();
        dpOdd.clear();
        for (const [k, v] of nextEven) dpEven.set(k, v);
        for (const [k, v] of nextOdd) dpOdd.set(k, v);
    }
    let ans = 0;
    if (dpEven.has(0)) ans = Math.max(ans, dpEven.get(0));
    if (dpOdd.has(0))  ans = Math.max(ans, dpOdd.get(0));
    return ans;
}

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin, output: process.stdout });
let lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const values = lines[1].split(/\s+/).map(Number);
    console.log(evenOddSumEquilibrium(values));
});