Maximum Prefix Subarray Sum — Problem Statement & Solution Guide

#include <bits/stdc++.h>
using namespace std;
long long maxPrefixSubarraySum(const vector<int>& nums, const vector<int>& pref){
    int n = nums.size();
    int m = pref.size();
    if(m==0) return 0; // empty prefix yields any subarray, choose max subarray sum (Kadane)
    // prefix sums of nums
    vector<long long> prefSum(n+1,0);
    for(int i=0;i<n;++i) prefSum[i+1]=prefSum[i]+nums[i];
    // suffix maximum of prefSum
    vector<long long> suffixMax(n+2,LLONG_MIN);
    suffixMax[n]=prefSum[n];
    for(int i=n-1;i>=0;--i) suffixMax[i]=max(prefSum[i],suffixMax[i+1]);
    long long best = LLONG_MIN;
    for(int i=0;i+ m <= n; ++i){
        bool ok=true;
        for(int k=0;k<m;++k){
            if(nums[i+k]!=pref[k]){ ok=false; break; }
        }
        if(!ok) continue;
        // we need max_{j >= i+m-1} sum(i..j) = max_{t >= i+m} prefSum[t] - prefSum[i]
        long long candidate = suffixMax[i+m] - prefSum[i];
        best = max(best, candidate);
    }
    if(best==LLONG_MIN) return 0; // pref not found
    return best;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<int> nums(n);
    for(int i=0;i<n;++i) cin>>nums[i];
    int m; cin>>m;
    vector<int> pref(m);
    for(int i=0;i<m;++i) cin>>pref[i];
    cout<<maxPrefixSubarraySum(nums,pref);
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    static long maxPrefixSubarraySum(int[] nums, int[] pref) {
        int n = nums.length;
        int m = pref.length;
        if (m == 0) return 0L;
        long[] prefSum = new long[n + 1];
        for (int i = 0; i < n; i++) prefSum[i + 1] = prefSum[i] + nums[i];
        long[] suffixMax = new long[n + 2];
        Arrays.fill(suffixMax, Long.MIN_VALUE);
        suffixMax[n] = prefSum[n];
        for (int i = n - 1; i >= 0; i--) {
            suffixMax[i] = Math.max(prefSum[i], suffixMax[i + 1]);
        }
        long best = Long.MIN_VALUE;
        outer:
        for (int i = 0; i + m <= n; i++) {
            for (int k = 0; k < m; k++) {
                if (nums[i + k] != pref[k]) continue outer;
            }
            long candidate = suffixMax[i + m] - prefSum[i];
            if (candidate > best) best = candidate;
        }
        return best == Long.MIN_VALUE ? 0L : best;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] nums = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int[] pref = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) pref[i] = Integer.parseInt(st.nextToken());
        System.out.println(maxPrefixSubarraySum(nums, pref));
    }
}

import sys

def max_prefix_subarray_sum(nums, pref):
    n = len(nums)
    m = len(pref)
    if m == 0:
        return 0
    # prefix sums
    pref_sum = [0]
    for x in nums:
        pref_sum.append(pref_sum[-1] + x)
    # suffix max of prefix sums
    suffix_max = [float('-inf')] * (n + 2)
    suffix_max[n] = pref_sum[n]
    for i in range(n - 1, -1, -1):
        suffix_max[i] = max(pref_sum[i], suffix_max[i + 1])
    best = None
    for i in range(n - m + 1):
        if nums[i:i + m] != pref:
            continue
        candidate = suffix_max[i + m] - pref_sum[i]
        if best is None or candidate > best:
            best = candidate
    return best if best is not None else 0

def main():
    data = list(map(int, sys.stdin.read().strip().split()))
    if not data:
        return
    it = iter(data)
    n = next(it)
    nums = [next(it) for _ in range(n)]
    m = next(it)
    pref = [next(it) for _ in range(m)]
    print(max_prefix_subarray_sum(nums, pref))

if __name__ == "__main__":
    main()

// Node.js solution
function maxPrefixSubarraySum(nums, pref) {
    const n = nums.length;
    const m = pref.length;
    if (m === 0) return 0; // empty prefix, any subarray – choose max subarray sum (Kadane) but not required here
    const prefSum = new Array(n + 1).fill(0n);
    for (let i = 0; i < n; ++i) prefSum[i + 1] = prefSum[i] + BigInt(nums[i]);
    const suffixMax = new Array(n + 2).fill(-9223372036854775808n);
    suffixMax[n] = prefSum[n];
    for (let i = n - 1; i >= 0; --i) {
        suffixMax[i] = prefSum[i] > suffixMax[i + 1] ? prefSum[i] : suffixMax[i + 1];
    }
    let best = -9223372036854775808n;
    outer: for (let i = 0; i + m <= n; ++i) {
        for (let k = 0; k < m; ++k) {
            if (nums[i + k] !== pref[k]) continue outer;
        }
        const candidate = suffixMax[i + m] - prefSum[i];
        if (candidate > best) best = candidate;
    }
    if (best === -9223372036854775808n) return 0;
    return Number(best);
}
function main(){
    const fs = require('fs');
    const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
    let p=0;
    const n=data[p++];
    const nums=data.slice(p,p+n); p+=n;
    const m=data[p++];
    const pref=data.slice(p,p+m);
    console.log(maxPrefixSubarraySum(nums,pref).toString());
}
main();