Problem: Given an array with size$\ n $: for each$\ a[i] $, it denotes the value of the house. You are given the task to build the wall that saves the house that is not exceed$\ w $ length. What is the maximum value you can save?
$\ 1<=n<=6,000,000 $;
$\ -500,000<=a[i]<=500,000 $;
For instance: n = 7, w = 3
3 2 5 1 4 -7 10
So the maximum value will be 10 and the maximum size will be 1 (10) or 3 (5 1 4). but the answer must be the minimum of length if there are more than one possible answers. So the length will be 1.
Is there anyway to achieve this using segment tree?
I have tried: Maximum subsegment sum using the prefix and suffix sum. But I cannot find the length.