Make array positive!

Revision en2, by eleganc, 2023-06-18 13:38:52

Given an array of length n. The task is to make the sum of all the subarrays of length greater than two positive. To do this, you can replace any element with any integer x where -10^18 < x < 10^18. Find the minimum number of replacements needed to make the array positive.

Constraints: -10^9 < arr[i] < 10^9 and n < 10^5

Example:

Test Case 1: Arr = [-80 100 -80] Ans = 1

Test Case 2: Arr = [-10 19 -10 2] Ans = 1 (by making arr[2] = 10^18)

Tags dp, array, implementations

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English eleganc 2023-06-18 13:38:52 2 Tiny change: '] = 10^18)' -> '] = 10^18)\n' (published)
en1 English eleganc 2023-06-18 13:38:16 480 Initial revision (saved to drafts)