3952. Maximum Total Value of Covered Indices

You are given an integer array nums of length n and a binary string s of length n, where s[i] == '1' means index i initially contains a token and s[i] == '0' means it does not.

You may perform the following operation any number of times:

• Choose a token currently located at index i, where i > 0, such that this token has not been moved before.
• Move this token from index i to index i - 1.

An index is considered covered if it contains a token after all moves.

Return an integer denoting the maximum total value of nums at the covered indices after optimally performing the operations.

class Solution {
public:
    long long maxTotal(vector<int>& nums, string s) {
        long long n = nums.size();
        vector<vector<long long>> dp(2, vector<long long>(n));
        for(int i = 0; i < n; i++) {
            if(s[i] == '1') {
                if(!i) dp[1][i] = nums[i];
                else {
                    dp[1][i] = max(max(dp[0][i-1],dp[1][i-1]) + nums[i], dp[0][i-1] + nums[i-1]);
                    dp[0][i] = dp[0][i-1] + nums[i-1];
                }
            } else {
                if(i) dp[0][i] = max(dp[0][i-1], dp[1][i-1]);
            }
        }
        return max(dp[0].back(), dp[1].back());
    }
};