How to find maximum sum subarray of size between [L, R]

Question

Given an array of both positive and negative integers, how would one find the maximum sum subarray (contiguous subarray) of length between L and R inclusive?

For example: If the array is

-1 3 -2 5 3 -5 2 2

and L = 1 and R = 2, the answer would be 8.

My Approach:

I am not too sure how to approach this question. I thought maybe it is a combination of sliding window + Kadane's. I have heard that prefix sums + sliding window might be a possible solution, but I am not sure how to implement it.

Answer 1

#include<bits/stdc++.h>
using namespace std;
#define maxn 10000
int a[maxn];

struct nod {
    int sum, prefixsum, suffixsum, maxsum;
};

nod tree[4*maxn];

Then I try to build segment tree:

inline void build(int l,int r,int node)
{

    if (l == r)
    {
        tree[node].sum=a[l];
        tree[node].prefixsum=a[l];
        tree[node].suffixsum=a[l];
        tree[node].maxsum=a[l];
        return;
    }

    int mid=(l+r)/2;
    int left=2*node;
    int right=2*node+1;
    build(l,mid,left);
    build(mid+1,r,right);
    tree[node].sum=tree[left].sum+tree[right].sum;

    tree[node].prefixsum=max(tree[left].prefixsum,tree[left].sum
    +tree[right].prefixsum);
    
    tree[node].suffixsum=max(tree[right].suffixsum,tree[right].sum+tree[left].suffixsum);
    
    tree[node].maxsum=max(tree[node].prefixsum,
        max(tree[node].suffixsum,max(tree[left].maxsum,
        max(tree[right].maxsum,tree[left].suffixsum+tree[right].prefixsum  ))));
}

Then I apply this query:

nod query( int index, int low, 
int high, int l, int r{

nod result;
result.sum = result.prefixsum = 
             result.suffixsum = 
             result.maxsum = INT_MIN;


if (r < low || high < l)
    return result;


if (l <= low && high <= r)
    return tree[index];

int mid = (low + high) / 2;

if (l > mid)
    return query( 2 * index + 1, 
                 mid + 1, high, l, r);
      

if (r <= mid)
    return query( 2 * index , 
                 low, mid, l, r);

nod left = query(2 * index , 
                  low, mid, l, r);
nod right = query( 2 * index + 1, 
                    mid + 1, high, l, r);


result.sum = left.sum + right.sum;
result.prefixsum = max(left.prefixsum, left.sum + 
                       right.prefixsum);
                         
result.suffixsum = max(right.suffixsum,
                   right.sum + left.suffixsum);
result.maxsum = max(result.prefixsum,
                max(result.suffixsum,
                max(left.maxsum,
                max(right.maxsum,
                left.suffixsum + right.prefixsum))));
                  
return result;
}

The main section:

int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
}
build(1,n,1);

 cout<< query(1,1,n,2,8).maxsum<<endl;

    
 cout<< query(1,1,n,1,2).maxsum<<endl;

}

Answer 2

I used divide and conquer approach explained in Cormen to solve this problem. Divide the array in half. For a small array say for size 2 the maximum subarray will be either the left half, or the right half, or the crossing containing both elements for the left half and right half.
for eg If arr[]={-3,5} right half is maximum subarray. If arr[]={3,6} crossing containing both elements of the left half and right half have maximum subarray. So solving this by using the divide and conquer paradigm we get the maximum subarray. Its working like this image posted here Implementation in c++

#include <bits/stdc++.h> 
typedef long long int ll;
using namespace std;
tuple<int ,int, int> Find_Crossing(int arr[],int low,int high);

tuple<int ,int, int> Maximum(int arr[],int low,int high)
{
    cout<<low<<" "<<high<<"\n";
    
    if(low==high)
        return make_tuple(low,high,arr[low]);
    else
    {
    int mid=(low+high)/2;
    int left_low,left_high,left_sum;
    tuple <int ,int ,int > left_ans;
    
    left_ans=Maximum( arr,low,mid);
    tuple <int ,int ,int >right_ans;
    right_ans=Maximum( arr,mid+1,high);
    tuple <int ,int ,int >cross_ans;
    
    cross_ans=Find_Crossing( arr,low,high);
    
    left_sum=get<2>(left_ans);
    
    int right_sum=get<2>(right_ans);
    int cross_sum=get<2>(cross_ans);
    if(left_sum>=right_sum&&left_sum>=cross_sum)
    {
        return left_ans;
    }
    if(right_sum>=cross_sum&&right_sum>=left_sum)
    {
        return right_ans;
    }

    return cross_ans;
    }
}

tuple<int ,int, int> Find_Crossing(int arr[],int low,int high)
{
    cout<<low<<" "<<high<<"\n";
    if(low==high)
        return  make_tuple(low,high,arr[low]);
    int mid=(low+high)/2;
    int l_max=INT_MIN;
    int sum=0;
    int l_index=mid;
    for (int i = mid; i >=low ; --i)
    {
        sum+=arr[i];
        if(sum>l_max)
            {
                l_max=sum;
                l_index=i;
            }   
    }

    int r_max=INT_MIN;
     sum=0;
    int r_index=mid+1;
    for (int i = mid+1; i <=high; ++i)
    {
        sum+=arr[i];
        if(sum>r_max)
        {
            r_max=sum;
            r_index=i;
        }
    }
    //cout<<l_index<<" ";
    
    return make_tuple(l_index,r_index,r_max+l_max);
}
int main()
{   

    int arr[] = {13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
    tuple<int,int,int> trying;
    trying= Maximum(arr,0,sizeof(arr)/sizeof(arr[0])-1);
    cout<<get<2> (trying);
}

Answer 3

Calculate prefix sum and then Iterate over indices(indices >= L && indices <= size of the array). And keep maintaining the minimum value of the prefix sum array which is far from current indices at least L distance but not far R distance(Which is done by sliding window concept) and Keep calculating the answer.

Answer 4

If I understand your problem correctly, there is an n*logn solution, which indeed uses prefix sums and sliding windows. Here it is explained: https://www.geeksforgeeks.org/maximum-sum-subarray-of-size-range-l-r/