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.

Improve this question
$\endgroup$
10
  • 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$ Commented Apr 10, 2019 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$ Commented Apr 10, 2019 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$ Commented Apr 10, 2019 at 18:01
  • $\begingroup$ Is this a problem in an ongoing programming contest? $\endgroup$ Commented Apr 11, 2019 at 4:32
  • $\begingroup$ No. this is the problem 2 years ago in my country. $\endgroup$ Commented Apr 11, 2019 at 4:58

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.