I think greedy is enough for this problem


  • 0
    Z

    I saw some DP and Divide and Conquer solutions, it looks like a simple for loop to check the prefix value is enough.


  • 0
    M

    You are right that it is enough to solve it, but the DP and divide and conquer solutions are based on the "more practice" slot. Once you solve the solution in O(n) using the for loop and prefix value, the problem challenges you to solve it using divide and conquer, which has a less straightforward approach, and so is more difficult.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.