1樓：焦子南
補充一些細節。
首先證明「子集和問題」可以歸約為「均分問題」。子集和問題是給定 n 個正整數和乙個正整數 m ，問能否從 n 個數中取出一些數使其和為 m 。用 (A, m) 表示子集和問題的輸入，其中 A 是長度為 n 的正整數列。
均分問題是給定 n 個正整數，問能否將這些數分成兩部分，使它們各自的和相等。用 A 表示均分問題的輸入，其中 A 是長度為 n 的正整數列。
注意均分問題顯然可以歸約為子集和問題（不過這不是我們需要的），但反過來則需要說明。任給乙個子集和問題的輸入 I=(A, m) ，計算 A 中所有數之和 S ，將 J=A 作為均分問題的輸入，則 I 滿足子集和問題，當且僅當 J 滿足均分問題。這就完成了將子集和問題歸約為均分問題的過程。
接下來將均分問題歸約為題主所述的問題。題主的問題不是判定性問題，但是很容易找到相應的判定性問題：給定 n 個整數和乙個整數 m ，問能否將 n 個數重排，使新數列字首和絕對值的最大值小於等於 m 。
不妨將該問題稱為「字首和問題」。用 (A, m) 表示字首和問題的輸入，其中 A 是長度為 n 的正整數列。
之後將均分問題歸約為字首和問題，這個其他回答已經提到了。任給乙個均分問題的輸入 I=A ，計算 A 中所有數之和 S ，將 J=(A, S/2) （其中 S/2 取下整）作為字首和問題的輸入，則 I 滿足均分問題，當且僅當 J 滿足字首和問題。歸約過程完成。
因為子集和問題是 NPC 問題，所以字首和問題是 NP-hard 問題（實際上字首和問題也是 NP 問題，只要將 n 個數重排的順序作為證書即可；因此，字首和問題是 NPC 問題），從而不太可能在多項式時間內解決。
題主的問題比「字首和問題」（指剛剛提到的判定性問題）要強，因為若求得字首和絕對值最大值的最小值，立即可以解決「字首和問題」。所以題主的問題也不太可能在多項式時間內解決。
2樓：nothing100
資料範圍小的時候可以考慮暴搜O(n!)或者去dp一下——dp[現在已經用了哪幾個數]，儲存值為字首最大值O(2^n*n)。
3樓：王贇 Maigo
我來解釋一下 @趙金昊 構造的例子。
假設已知的數中有且僅有乙個負數 -2N，另外的數都是正數，且和為 2N。
如果這些正數中有若干個相加等於 N，那麼就可以構造這樣乙個排列：相加等於 N 的數排在前面，然後排 -2N，再把另外一些數排在後面。這樣，「字首和的絕對值」最大是 N。
如果這些正數中沒有任意乙個子集相加等於 N，則上面這件事做不到，「字首和的絕對值」必然在某個時刻大於 N。
而「判斷一些數中有沒有乙個子集相加等於給定值」（稱為「子集和問題」）是乙個 NPC 問題，題主的問題可以化歸為子集和問題，所以沒有多項式時間的解。
4樓：趙金昊
NPC的，別想啦。
搞個-2N，以及若干個和為2N的數，不是分分鐘變成子集和問題嘛。
所以解題思路只有一種，就是看數的大小。如果不超過10的話還是可做的……
從N個數 N很大 中隨機取k個不重複數有什麼方法？
夜清凌 計算機題目嗎？取數字放進Set裡？比如 while k 0 random 1,N i set.put i false?continue k 程式設計思維 如果n很大，而k很小，比如在1億個數裡面挑5個數，random shuffle 是對這n個數進行亂序，然後再找出5個數，速度當然會很慢，時...
有乙個有口音的老師怎樣一種體驗？
伯納烏的貓咪 本人西班牙語專業大一狗，聽力課老師是個正宗的廣東廣府人，講的港普，有次上課，叫我們發大舌音 顫音 第一句話就是 李們要控記一sia石頭 你們要控制一下舌頭 我大學，有個老師，湖南的，普通話極其不標準。有次上課，他講相襯顯微鏡，我們聽的都是 鄉村小味精。全程不知所云。當然了，那門課大家後...
有乙個外國老公是一種什麼體驗？
大師兄快樂一家人 我和老公認識得比較久，大學時候認識的，後來一起讀了研究生。剛開始認識他的時候，就是覺得他很幽默，很體貼，三觀比較契合。會盡能力 寵 著我，考慮我的感受，比我受寵的是兒子。一起健身。一起帶娃。一起做菜，一起吃飯。剛認識的樣子。近照。很少有 孤獨 的時候，話不用多說，乙個眼神就能懂對方...