Kadane’s Algorithm

現在的自己就是過去最好自己的卷積
進步就是要比過去最好的自己還要好
– Kadane’s Algorithm

背景知識

• 基礎程式語法
• Greedy Strategy
• Kadane’s Algorithm

理解問題

給定一array, 找連續子序列總和最大值

如果要程式化，我們可能會從頭一個個找值加後續直到結尾，我們可能需要三個迴圈，1尋訪各元素，2從該元素到結尾，3加總，是cube時間，而最長子序列問題已經有常用解法了。

Kadane算法常用來解決最長子序列問題，也是動態規劃的一種。
53. Maximum Subarray
3. Longest Substring Without Repeating

思路視覺化

只要加入後是負值就捨去
nums = [-2,1,-3,4,-1,2,1,-5,4]
-2+1<0 
1+(-3)<0
(-3)+4>0 ->4之前都捨去
4+(-1)= 3
3+2= 5
5+1= 6
6+(-5)= 1
1+4= 5
 
所以最大的連續子序列[4,-1,2,1] 總和= 6

Java

TC: O(n)
SC: O(n)

import java.util.*;
public class Kadane {
    private static int kadne(int[] nums){
        /*
        int prev, history;
        prev = history = nums[0];
        */
        int prev = nums[0], history = nums[0];
        
        for(int i = 1; i<nums.length; i++){
            prev = Math.max(nums[i], nums[i]+ prev);
            history = Math.max(prev, history);
            System.out.println(prev+" "+history+"\n");
        }
        return history;
    }
    public static void main(String args[]) {
        int [] nums = {-2,1,-3,4,-1,2,1,-5,4};
        int res = kadne(nums);
        System.out.println("Maximum: "+res);
   }
}
>
java -cp /tmp/CSqCzH62b6 Kadane
1 1
-2 1
4 4
3 4
5 5
6 6
1 6
5 6
Maximum: 6

Python

def kadane(nums):
    history = prev = nums[0]
    for i in range(1, len(nums)):
        prev = max( nums[i], nums[i]+ prev) # local maximum
        history = max(prev, history)
    return history

問題

1. ZeroOne Knapsack
2. Unbound Knapsack

下次再介紹幾題好了

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)