網路上講義裡附的題目
題目：
有N個正整數，請問所有總和<=M的區間和中，最大的是多少。
做法：
由於數字都是正的，可以看到一個簡單的性質:
如果左端點固定的話，右端點愈向右延伸總和會愈大
於是我們將這N個數字視為N個左端點去求解
對於每個左端(L)，右端(R)延伸到盡頭(>M)為止，沿路加總，更新答案
然後L右移一格重新執行下一組
而這裡我們可以發現:
對於這個L找到的盡頭R，當L右移一格後，加總的和會扣除value[L]，總和只會減小
也就是下一組的R只要繼續往右延伸即可，不用從頭跑，因為上一組的總和<=M，這組扣掉value[L]必也會<=M
於是兩個指針從最左掃到最右
因為總共只會掃過一遍，複雜度O(N)
code:
對於每個左端(L)，右端(R)延伸到盡頭(>M)為止，沿路加總，更新答案
然後L右移一格重新執行下一組
而這裡我們可以發現:
對於這個L找到的盡頭R，當L右移一格後，加總的和會扣除value[L]，總和只會減小
也就是下一組的R只要繼續往右延伸即可，不用從頭跑，因為上一組的總和<=M，這組扣掉value[L]必也會<=M
於是兩個指針從最左掃到最右
因為總共只會掃過一遍，複雜度O(N)
code:
沒有留言:
張貼留言