JZ85 連續子陣列的最大和(二)
題目
輸入一個長度為n的整型陣列array，陣列中的一個或連續多個整陣列成一個子陣列，找到一個具有最大和的連續子陣列，
1.子陣列是連續的，比如[1,3,5,7,9]的子陣列有[1,3]，[3,5,7]等等，但是[1,3,7]不是子陣列
2.如果存在多個最大和的連續子陣列，那么回傳其中長度最長的，該題資料保證這個最長的只存在一個
3.該題定義的子陣列的最小長度為1，不存在為空的子陣列，即不存在[]是某個陣列的子陣列
4.回傳的陣列不計入空間復雜度計算
方法 動態規劃
思路
演算法實作
既然是連續子陣列，如果我們拿到了當前的和，對于后面一個即將加入的元素，如果加上他這一串會變得更大，我們肯定會加上它，
如果它自己會比加上前面這一串更大，說明從它自己開始連續子陣列的和可能會更大，
具體做法：
step 1：創建動態規劃輔助陣列，記錄到下標i為止的最大連續子陣列和，下標為0的時候，肯定等于原陣列下標為0的元素，
step 2：準備左右區間雙指標記錄每次連續子陣列的首尾，再準備兩個雙指標記錄最大和且區間最長的連續子陣列的首尾，
step 3：遍歷陣列，對于每個元素用上述狀態轉移公式記錄其dp值，更新區間首尾（如果需要），
step 4：出現一個最大值，且區間長度更大的時候，更新記錄最長區間的雙指標，
step 5：根據記錄的最長子陣列的位置取陣列，
代碼
package mid.JZ85連續子陣列的最大和2;
import java.util.*;
public class Solution {
/**
* 代碼中的類名、方法名、引數名已經指定，請勿修改，直接回傳方法規定的值即可
*
* @param array int整型一維陣列
* @return int整型一維陣列
*/
public int[] FindGreatestSumOfSubArray(int[] array) {
// write code here
if (array.length == 1) return array;
int[] dp = new int[array.length];
dp[0] = array[0];
int max = dp[0];
//滑動區間
int left = 0, right = 0;
//記錄最長區間
int resl = 0, resr = 0;
for (int i = 1; i < array.length; i++) {
right++;
dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
if (dp[i - 1] + array[i] < array[i]) {
//如果左邊加起來還沒有這個值大，那么重新定義left為這個值
left = right;
}
if (dp[i] > max || dp[i] == max && (right - left + 1) > (resr - resl + 1)) {
max = dp[i];
resl = left;
resr = right;
}
}
int[] res = new int[resr - resl + 1];
for (int i = resl; i <= resr; i++) {
res[i - resl] = array[i];
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/541342.html
標籤：其他
下一篇：Python工具箱系列(二十一)