Pattern mountain prob

#21

run time error is because you are trying to access the address which doesn’t exist now.

#22

Now i understand why run time error

#23

Great :slight_smile:

#24

  1. I understand kadane algorithm but why it works

  2. chrome
    chrome2160×1080 224 KB
    and also unable to understand this method

#25

Tip: It’s usually easy to proof by contradiction. Ignore the rest if you liked the suggestion.

Suppose you found some ans using your algorithm and ans is not the biggest.

If it’s not the biggest, it means at some point, your ans was compared to a value X that’s bigger than ans and max(ans, X) returned you ans.

Since max returns only the maximum value and X is bigger than ans, it’s a contradiction.

By induction in the size n of the array, it’s quite easy:

Base case: n = 1

the algorithm will run and return the only element who is also the biggest [OK]
Hypohtesis: The algorithm works for any n

Inductive Step: It works for n+1

Let’s say you runned the first n elements of the array and you have your ans.

Now you will just compare ans with the last element and you will return the biggest.

As ans was the biggest from the first n elements (by hypothesis, we can find the biggest between n elements) and ans will be the maximum between ans and the last element, ans will be the maximum of the full array. [OK]

hope it helps.