這就是問題：
給定一個整數的 ArrayList，找到一個具有 ArrayList 中任何潛在子陣列的最大總和的子陣列。子陣列是連續數字的任意組合。子陣列可以是任意長度 n，其中 n >= 0 的大小。
示例：輸入給定 = [-1, 10, -11, -1, 17, 0, 0, 9, 20, 7, -8, -6, -18] 解決方案 = [17, 0, 0, 9, 20 , 0, 7]
我已經在這幾個小時了，我已經筋疲力盡了！這是我到目前為止的代碼
import java.util.ArrayList;
public class MaxSubArray {
public ArrayList<Integer> solution(ArrayList<Integer> nums) {
int maxSubArrSum = Integer.MIN_VALUE;
int greatest = Integer.MAX_VALUE;
int smallest = 0;
int start;
int end;
ArrayList<Integer> maxSubArr;
ArrayList<ArrayList<Integer>> lists = new ArrayList();
try {
for (int left = 0; left < nums.size(); left ) {
int runningSum = 0;
for (int right = left; right < nums.size(); right ) {
runningSum = nums.get(right);
if (runningSum >= maxSubArrSum) {
ArrayList<Integer> temp = new ArrayList<>();
maxSubArrSum = runningSum;
start = left;
end = right;
for (int i = start; i <= end; i ) {
temp.add(nums.get(i));
}
lists.add(temp);
}
}
}
for (int i = 0; i < lists.size(); i ) {
if (lists.get(i).size() < greatest) {
greatest = lists.get(i).size();
smallest = i;
}
}
maxSubArr = lists.get(smallest);
return maxSubArr;
} catch (Exception e) {
e.printStackTrace();
return nums;
}
}
}
我正在嘗試遍歷 nums ArrayList 并找出具有最大總和的子陣列的第一個和最后一個索引，并將它們放入 arrayLists 串列中。之后，我試圖找出哪個是最小大小的子陣列并回傳它。有誰看到我在這里做錯了什么？
uj5u.com熱心網友回復：
你安靜地接近你的方法。最后一部分有兩個問題：
int greatest = Integer.MAX_VALUE;應該Integer.MIN_VALUE改為。- 您檢查子陣列的大小，但必須檢查子陣列的總和。
如果您將最后一部分更改為：
int greatest = Integer.MIN_VALUE;
for (int i = 0; i < lists.size(); i ) {
if (sum(lists.get(i)) > greatest) {
greatest = lists.get(i).size();
smallest = i;
}
}
通過利用
public static int sum(List<Integer> arr) {
int sum = 0;
for(int a : arr){
sum = a;
}
return sum;
}
它產生了預期的結果。
uj5u.com熱心網友回復：
這是一個更簡潔的解決方案
private List<Integer> solution(List<Integer> nums) {
int biggestSumSoFar = Integer.MIN_VALUE;
List<Integer> biggestSubListSoFar = new ArrayList<>();
for (int left = 0; left < nums.size(); left) {
for (int right = left 1; right < nums.size(); right) {
List<Integer> currentSubList = subListSum(nums, left, right);
int currentSum = sum(currentSubList);
if (currentSum > biggestSumSoFar) {
biggestSumSoFar = currentSum;
biggestSubListSoFar = currentSubList;
}
}
}
return biggestSubListSoFar;
}
private List<Integer> subListSum(final List<Integer> nums, final int left, final int right)
{
final List<Integer> sublist = new ArrayList<>();
for (int i = left; i < right; i )
{
sublist.add(nums.get(i));
}
return sublist;
}
private int sum(List<Integer> arr) {
int sum = 0;
for(int a : arr){
sum = a;
}
return sum;
}
uj5u.com熱心網友回復：
添加第三個內部 for 回圈可能會使任務更容易。想想你會如何用筆和紙來做。想象一下，您有一個包含 6 個元素的陣列，其索引為0to 5，那么所有可能的子陣列都將具有以下開始和結束索引（包括 strat，不包括結束）
0 - 1 1 - 2 2 - 3 3 - 4 4 - 5
0 - 2 1 - 3 2 - 4 3 - 5
0 - 3 1 - 4 2 - 5
0 - 4 1 - 5
0 - 5
擁有以上所有內容，您需要計算子和并存盤相關的開始和結束索引
public List<Integer> solution(List<Integer> nums) {
int maxSubArrSum = Integer.MIN_VALUE;
int start = 0;
int end = 0;
for (int left = 0; left < nums.size(); left ){
for (int right = left 1; right < nums.size(); right ){
int subSum = 0;
for (int k = left; k < right; k ){
subSum = nums.get(k);
}
if (subSum > maxSubArrSum){
maxSubArrSum = subSum;
start = left;
end = right;
}
}
}
return nums.subList(start,end);
}
uj5u.com熱心網友回復：
它可以在O(n)的時間和空間內完成，并且代碼更易于理解。
這種方法只需要對源串列進行兩次迭代。
為此，您首先需要使用 Kadane 演算法計算最大可能的總和。
然后遍歷跟蹤當前總和的源串列，當它等于最大總和時，意味著找到了連續元素的目標集。
public static void main(String[] args) {
List<Integer> source = List.of(-1, 10, -11, -1, 17, 0, 0, 9, 20, 7, -8, -6, -18);
System.out.println(solution(source));
}
public static List<Integer> solution(List<Integer> nums) {
if (nums.size() == 0) {
return Collections.emptyList();
}
List<Integer> result = new ArrayList<>();
result.add(nums.get(0));
final int maxSum = getMaxSum(nums); // getting max sum by using Kadane's algorithm
int curSum = nums.get(0);
for (int i = 1; i < nums.size(); i ) {
if (curSum == maxSum) {
break; // maximus sub-array was found
}
if (nums.get(i) > curSum nums.get(i)) {
result = new ArrayList<>();
curSum = nums.get(i);
} else {
curSum = nums.get(i);
}
result.add(nums.get(i));
}
return result;
}
public static int getMaxSum(List<Integer> nums) {
int maxSum = Integer.MIN_VALUE;
int curSum = nums.get(0);
for (int i = 1; i < nums.size(); i ) {
curSum = Math.max(nums.get(i), curSum nums.get(i));
maxSum = Math.max(maxSum, curSum);
}
return maxSum;
}
輸出
[17, 0, 0, 9, 20, 7]
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/447978.html