檢查算法的最小跳轉數的正確性

Question

我有一個算法是基於一個問題，你需要找到最小數量的跳轉到達數組的末尾。這個問題被問到極客對於極客，他們沒有線性時間算法在我的情況下算法是在線性時間，但測試用例會我的算法失敗？ .The鏈接問題

鏈接： - http://www.geeksforgeeks.org/minimum-number-of-jumps-to-reach-end-of-a-given-array/

輸入：常用3 [] = {1，3，5，8，9，圖2，圖6，圖7，圖6，圖8，9}

• 從第一個元素開始我們知道，該元件的最大範圍是1，因此，使得來自1-> 3

• 現在，在第二步驟中，我們知道的範圍，我們可以向前移動只有一步元素是3，因此從那一步開始，我們從3那裏計算最大值我們可以選擇5,8,9，在這個範圍內的最大值是9

• 因此，先移動到9即1-> 3-> 9，然後從9我們移動到數組的末尾知道九步足以達到目的。

• 拐角的情況是，如果我們在最後檢測到一個零點，我們什麼都不做，因爲我們已經達到了結束點。但是如果在開始時檢測到零或者在該範圍內的最大元素爲0向前移動，我們返回-1，因爲我們無法進一步移動請告訴我，如果此算法中存在錯誤。

Answer 1

是的，這個算法不起作用。例如：

arr[] = {5,2,1,1,1,1,1} 

你的算法將看到5，則看到最大數量2，然後進入1 1 1 1。即： 5,2,1,1,1,1 = 6的跳躍。

雖然最佳的結果是：5 - > 1（第二從端） - > 1 = 3跳