0
$\begingroup$

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?

Constraint:

$\ 1<=n<=6,000,000 $;

$\ -500,000<=a[i]<=500,000 $;

$\ 1<=w<=100,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.

$\endgroup$
  • 1
    $\begingroup$ Welcome to Computer Science! Could you please format your question as text (and not a bullet point list) so it is more understandable? Also, I believe your question would benefit greatly from adding some more context (i.e., why is it an interesting question?). Thank you. $\endgroup$ – dkaeae Apr 10 at 16:13
  • 2
    $\begingroup$ What is $q$ and how does it relate to this problem? Why do you want to use a segment tree? I feel this could be done easily with a sliding window implemented as a deque. What have you tried so far, in regards to using a segment tree? $\endgroup$ – ryan Apr 10 at 17:16
  • 1
    $\begingroup$ Please edit the question to add a reference to the original problem you are asked to solve. A reference is especially helpful to avoid ambiguities and XY problem. $\endgroup$ – Apass.Jack Apr 10 at 18:01
  • $\begingroup$ Is this a problem in an ongoing programming contest? $\endgroup$ – Apass.Jack Apr 11 at 4:32
  • $\begingroup$ No. this is the problem 2 years ago in my country. $\endgroup$ – Chalanthorn Chanmathikornkul Apr 11 at 4:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.