class Solution {
    std::vector<int> expend(const std::vector<int>& nums){
        std::vector<int>res;res.reserve(2*nums.size()+3);
        res.push_back(-1);
        res.push_back(0);
        for(int i=0;i<nums.size();i++)res.push_back(nums[i]),res.push_back(0);
        res.push_back(-2);
        return res;
    }

    std::vector<int> Manacherss(const std::vector<int>& nums){
        auto t=expend(nums);
        std::vector<int>p(t.size());
        for(int i=1,r=0,c=0;i<t.size()-1;i++){
            p[i]=(r>i?std::min(p[2*c-i],r-i):1);
            while(t[i-p[i]]==t[i+p[i]])++p[i];
            if(i+p[i]>r)r=i+p[i],c=i;
        }
        return p;
    }
public:
    long long getSum(vector<int>& nums) {
        auto p=Manacherss(nums);
        std::vector<long long>pre(1+nums.size());
        for(int i=1;i<=nums.size();i++)pre[i]=pre[i-1]+nums[i-1];

        long long mx=0;
        for(int i=1;i<p.size()-1;i++){
            int str=(i-p[i])/2;
            int len=p[i]-1;
            int end=str+len-1;
            mx=std::max(mx,pre[end+1]-pre[str]);
        }

        return mx;
    }
};