全域檔案編號：1452
一、背景
一個朋友問了我這樣一個問題：給定一個整數陣列（有正數有負數），例如{-2,1,-3,4,-1,2,1,-5,4}，找出總和最大的連續數列，并回傳總和，覺得挺有意思，寫代碼實作了一下，
二、思路故事
類似于逛街買衣服，我們有明確的目標（例如：7分牛仔褲，類比于連續數列和最大），然后一家店一家店比價，比完價格最低的下單完事，
- 遍歷陣列，獲取其子陣列，并計算和
- 不斷冒泡，子陣列和更大的記錄其左右下標
- 遍歷結束，連續數列和最大結果揭曉
三、Java代碼實作
/**
* @author wangyao
* @date 2020-5-11 13:54
* @description:
*/
public class ArrayTest {
public static void main(String[] args) {
/**
* 給定一個整數陣列（有正數有負數），找出總和最大的連續數列，并回傳總和，
* 示例：
* 輸入： [-2,1,-3,4,-1,2,1,-5,4]
* 輸出： 6
* 解釋： 連續子陣列 [4,-1,2,1] 的和最大，為 6，
*/
int left = 0, right = 0, maxCount = 0, preLeft, preRight, preMaxCount = 0;
Integer[] a = {-2,1,-3,4,-1,2,1,-5,4};
Integer[] targetArray = {};
for (int i = 0; i < a.length; i++) {
for (int j = i; j < a.length; j++ ) {
preLeft = i;
preRight = j;
Integer[] childArray = Arrays.copyOfRange(a, i , j);
preMaxCount = Arrays.asList(childArray).stream().mapToInt(value -> value).sum();
if (preMaxCount > maxCount) {
left = preLeft;
right = preRight;
maxCount = preMaxCount;
targetArray = childArray;
}
}
}
System.out.println(left + "," + (right-1));
System.out.print("符合條件的連續子陣列為:");
Arrays.asList(targetArray).stream().forEach(integer -> System.out.print(integer.intValue() + ","));
System.out.print("最大值" + maxCount);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/21255.html
標籤：其他
上一篇：十個亂數，相加之和等于100，怎么分成相加之和等于50的兩組
下一篇：分析常用名詞含義 指標 維度