?

【試題描述】輸入一個(gè)整型數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中一個(gè)或連續(xù)的多個(gè)整數(shù)組成一個(gè)子數(shù)組。

求所有子數(shù)組的和的最大值。要求時(shí)間復(fù)雜度O(n)。

思路：當(dāng)我們加上一個(gè)正數(shù)時(shí)，和會(huì)增加；當(dāng)我們加上一個(gè)負(fù)數(shù)時(shí)，和會(huì)減少。如果當(dāng)前得到的和是個(gè)負(fù)數(shù)，那么這個(gè)和在接下來(lái)的累加中應(yīng)該拋棄并重新清零，不然的話這個(gè)負(fù)數(shù)將會(huì)減少接下來(lái)的和。

?

【參考代碼】

?

1 public static int maxSum(int[] a) { 2 int sum = 0; 3 int b = 0; 4 for (int i = 0; i < a.length; i++) { 5 if (b < 0) 6 b = a[i]; 7 else 8 b += a[i]; 9 if (sum < b) 10 sum = b; 11 } 12 return sum; 13 }

?

思路2：動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)

/*
*問(wèn)題：輸入一個(gè)整型數(shù)組，數(shù)組里有正數(shù)也有負(fù)數(shù)。數(shù)組中一個(gè)或連續(xù)的多個(gè)整數(shù)組成一個(gè)子數(shù)組。
*求所有子數(shù)組的和的最大值。要求時(shí)間負(fù)責(zé)度為O(n)。
*使用動(dòng)態(tài)規(guī)劃方法來(lái)實(shí)現(xiàn)：
*如果用函數(shù)f(i)表示以第i個(gè)數(shù)字結(jié)尾的子數(shù)組的最大和，那么我們需要求出max(f[0...n])。
*我們可以給出如下遞歸公式求f(i)
*???? |-- array[i] 如果i==0或者f(i-1)<0
*f(i)=|
*???? |-- f(i-1) + array[i] 如果f(i-1)>0
*這個(gè)公式的意義：
*?? 當(dāng)以第(i-1)個(gè)數(shù)字為結(jié)尾的子數(shù)組中所有數(shù)字的和f(i-1)小于0時(shí)，如果把這個(gè)負(fù)數(shù)和第i個(gè)數(shù)相加，得到的結(jié)果反而不第i個(gè)數(shù)本身還要小，所以這種情況下最大子數(shù)組和是第i個(gè)數(shù)本身。
*?? 如果以第(i-1)個(gè)數(shù)字為結(jié)尾的子數(shù)組中所有數(shù)字的和f(i-1)大于0，與第i個(gè)數(shù)累加就得到了以第i個(gè)數(shù)結(jié)尾的子數(shù)組中所有數(shù)字的和。
*/?

1 public static int maxSumInSubArray(int[] array) { 2 int[] c = new int[array.length];// 用來(lái)記錄以當(dāng)前元素結(jié)尾（數(shù)組就到當(dāng)前元素的位置為止）的子數(shù)組的最大和 3 int max = -1000;// 用來(lái)記錄數(shù)組c[]中的最大值 4 int start = 0;// 記錄數(shù)組中子數(shù)組的最大和的開始位置 5 int end = 0;// 記錄數(shù)組中子數(shù)組的最大和的結(jié)束位置 6 int tmp = 0; 7 8 c[0] = array[0]; 9 for (int i = 1; i < array.length; ++i) { 10 if (c[i - 1] > 0) { 11 c[i] = c[i - 1] + array[i]; 12 } else { 13 c[i] = array[i]; 14 tmp = i; 15 } 16 if (c[i] > max) { 17 max = c[i]; 18 start = tmp; 19 end = i; 20 } 21 } 22 System.out.println("子數(shù)組最大和的起始位置：" + start + "~" + end); 23 return max; 24 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/WayneZeng/p/9290767.html

總結(jié)

以上是生活随笔為你收集整理的【IT笔试面试题整理】连续子数组的最大和的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。