Блог пользователя samurai123

Автор samurai123, история, 8 лет назад, По-английски

I have solved the problem LINK with sliding window. But in comments, some people mentioned about solving it with binary search. What should be the search function for binary search in the problem? Can that function be made without using concept of sliding window.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Use binary search on the prefix sum and find the length of segment for each segment starting at position i. Time complexity is O(NlogN), I am not sure if there is another approach using binary search with a more decent time complexity though.