李素萍

（山西工程技術學院信息系，陽泉045000）

1 問題

給出一個整形數(shù)組，要求找出元素之和最大的子數(shù)組。

為了更精確地描述問題，定義數(shù)組元素A[0]=0，并用A[j:k]表示A 中從下標j 到下標k 的元素構成的子數(shù)組（0<=j<=k<=n）。最大子數(shù)組的問題是，求使得sj，k達到最大的子序列A[j:k]（0<=j<=k<=n），sj，k表示該段元素的和，這個最大和稱為A 的最大子數(shù)組和。為了簡單起見，該問題只限于求出最大子數(shù)組和（算法表示），這里不需求最大子數(shù)組A[j:k]的下標j 和k。

2 已有解法

算法1：

MaxsubSlow（A）:

輸入：n 個數(shù)的數(shù)組A，下標1 到n

輸出：A 的最大子數(shù)組和

m←A[1]//目前找到的最大和

for j←1 to n do

for k←j to n do

s←0//將要計算的下一部分和

for i←j to k do

s←s+A[i]

if s>m then

m←s

return m

算法2：

MaxsubFaster（A）:

輸入：n 個數(shù)的數(shù)組A，下標1 到n

輸出：A 的最大子數(shù)組和

S0←0//初始前綴和

for i←1 to n do

si←si-1+A[i]

m←A[1]//目前找到的最大和

for j←1 to n do

for k←j to n do

s←sk-sj-1

if s>m then

m←s

return m

算法3：

MaxsubFastest（A）:

輸入：n 個數(shù)的數(shù)組A，下標1 到n

輸出：A 的最大子數(shù)組和

m←A[1]

S←0

for i←1 to n do

If（s<0）s←0;

s←s+A[i]

If s>m then

m←s

return m

3 新解法

算法4：

Maxsubnew（A）:

輸入：n 個數(shù)的數(shù)組A，下標1 到n

輸出：A 的最大子數(shù)組和

A[0]←0

m←A[1]

for j←1 to n do

for i←j to n do

s←sum（i，A）-sum（j-1，A）

if（m

return m

用遞歸法求和算法：

int sum（int i，int A[n]）

{if（i==0）return 0;

if（i==1）return A[1];

else

return sum（（i-1），A）+A[i];

}

4 學習三階段

以上展示了從問題提出到各種解法的過程，下面還將對各種解法比較分析，目的是想證明學習三階段循環(huán)往復無限發(fā)展。

學習第一階段——知識認知階段：上面問題提到要求求出元素之和最大的子數(shù)組，學過計算機語言的人都知道這個問題需要用到數(shù)組知識解決，涉及到數(shù)組自然會用到循環(huán)結構，這就是解決這個問題用到的主要知識點，也就是說在學習計算機語言時會講到數(shù)據(jù)類型運算符表達式，順序結構分支結構循環(huán)結構、數(shù)組、函數(shù)等這些基本內(nèi)容，在學習這門課程的過程中如果不做太多練習或即使做了練習問題應用性不強又沒有對同一問題提出各種解法，對各種解法進行比較，對各種解法進行性能分析的話，對知識的認識基本還停留在認知階段，知道如何定義數(shù)組使用數(shù)組，以及使用數(shù)組的注意事項、技巧，等等，無法對知識認知深化，再認識，這樣學習就很枯燥，這樣的學習處于機械記憶被動接受階段，于是，遇到困難就可能選擇逃避甚至放棄。如果做練習時聯(lián)系實際，提出一題多解，要求對各種解法比較并分析性能的話，學習的過程就有了趣味性，由被動變主動，由要我做變?yōu)槲乙?，從而使學習的效率大大提高，學習的效果也非常好，這就是學習過程從知識認知階段轉化為知識應用階段的必然結果，對知識的認知由感性認識上升到了理性認識，由理解上升到了掌握進而能熟練應用。

學習第二階段——知識應用階段：如果我們告訴學生該問題可以用于數(shù)字化圖像模式識別，在運行時間和存儲空間等性能方面有具體要求的話，學生感覺知識有著落了，即使有困難也會嘗試挑戰(zhàn)自己解決問題的能力，于是就會找資料，復習舊知識，鞏固新知識，優(yōu)化解法，證明自己。學習過程從知識認知階段轉化到知識應用階段，實質上是對知識的認識到知識的使用的轉變，是從理論到實踐的轉變，是將知識轉化為產(chǎn)品的過程，這個過程既要對知識進行整合，又要對知識進行應用，這樣才能實現(xiàn)問題滿足用戶需求。例如算法1 使用了累加器設計模式，運行時間為O（n3），算法二引入了前綴和，即前t 個整數(shù)和st=a1+a2+...+an（t=1，2，...n.），就可以用該公式sj，k=sk-sj-1。在常數(shù)時間計算該任何子數(shù)組的和sj，k，從而使總運行時間變?yōu)镺（n2），比算法一改進了一個線性因子。算法三從實際輸入數(shù)據(jù)角度考慮，當數(shù)據(jù)序列中有負數(shù)的話，加入了s<0，則清零，從下一個數(shù)開始求和找出最大值，從而使總運行時間變?yōu)镺（n）?？梢妼W習階段轉換的必要性。既鍛煉了學生解決問題的能力，又給社會帶來了實際效益?！罢J識，實踐，再認識，再實踐”，學習過程形成良性循環(huán)，知識積累構成龐大體系，全方位發(fā)展，實現(xiàn)個人價值社會價值相統(tǒng)一。

這里，筆者再換一種思維方式求解，用遞歸法求和完成該問題，從而得到新的解法算法4。可以看到，這種解法在時間空間性能上并沒有優(yōu)化，但我提出用遞歸方法解決此問題并成功實現(xiàn)了這種思想，這就是求異思維。

求異思維是在思維中自覺地打破已有的思維定式、思維習慣或以往的思維成果，在事物各種巨大差異之間建立“中介”，突破經(jīng)驗思維束縛的思維方法。

求異思維重在開闊學生思路，啟發(fā)學生聯(lián)想，從各方面、各角度、各層次思考問題，并在各種結構的比較中，選擇富有創(chuàng)造性的異乎尋常的新構思。具有廣博的開拓創(chuàng)新性和遷延性，沖破陳舊的思維模式，把思維從狹窄、封閉、陳舊體系中解放出來，進而使學習過程上升為知識創(chuàng)新階段。

學習第三階段——知識創(chuàng)新階段：知識是人們在改造世界的實踐中所獲得的認識和經(jīng)驗的總和。知識創(chuàng)新包括科學知識創(chuàng)新、技術知識特別是高技術創(chuàng)新和科技知識系統(tǒng)集成創(chuàng)新等。知識創(chuàng)新的目的是追求新發(fā)現(xiàn)、探索新規(guī)律、創(chuàng)立新學說、創(chuàng)造新方法、積累新知識。有的時候靈感真的是瞬間的，就像牛頓在蘋果樹下被那個靈感蘋果所砸中，于是牛頓的大腦當中產(chǎn)生了這樣的火花，為什么蘋果會落地下呢，就這一碰撞，碰撞出了萬有引力這個基礎的新的知識點，如果牛頓當時沒有立即記下這個靈感或者說沒有將這個靈感付諸于實踐，那么這個知識是否會被世人發(fā)現(xiàn)呢？勤于思考，勇于實踐，敢于創(chuàng)新，善于開拓，由深到廣推動科技發(fā)展構建和諧社會，為實現(xiàn)“人類命運共同體”這一全球價值觀做出貢獻。

學習三階段缺一不可，構成相互依賴的統(tǒng)一體。知識感知階段是其他階段的基礎，正如本文算法4 要求用遞歸方法實現(xiàn)，如果沒有遞歸知識做基礎，那這種解法就無從談起，但如果學了一堆知識不去整合，不聯(lián)系實際解決問題的話，即知識感知階段不轉換為知識應用階段就無法證明知識的正確性，無法評價優(yōu)劣，實踐是認識的來源，也是檢驗真理的標準，經(jīng)過實踐檢驗發(fā)現(xiàn)紕漏提出新的解決問題的方法即知識創(chuàng)新，然后再應用于實踐檢驗，再創(chuàng)新，循環(huán)往復推動社會發(fā)展。這種“實踐、認識、再實踐、再認識”的無限發(fā)展過程，在形式上是循環(huán)往復，在實質上是前進上升，是由低級階段向高級階段不斷推移的永無止境的前進運動。只有這樣，才有可能實現(xiàn)科學研究、人才培養(yǎng)、社會服務等功能。