資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Java 中的最大子陣列和：Kadane 演算法
在這裡，我們將學習如何使用 Java 中的 Kadane 演算法查詢最大子陣列和？
問題陳述
給定一個大小為 N 的陣列，編寫一個 Java 程式，使用 Kadane 演算法查詢最大子陣列和。
示例
Input: n = 5 arr[] = 1, 2, 3, -2, 5 Output: Maximum Subarray sum is: 9
什麼是 Kadane 演算法
Kadane 演算法幫助我們以 O(n) 的時間複雜度找到最大子陣列和。
使用 Kadane 演算法查詢最大子陣列和的步驟
- 初始化兩個名為 currentSum=Integer.MIN_VALUE 和 maxSum= 0 的變數。
- 迭代陣列，從索引 0 到 n-1。
- 將每個索引的值 (arr[i]) 新增到 currentSum 中。
- 在每次迭代中更新 maxSum Math.max(maxSum, currentSum)。
- 檢查 currentSum 是否小於零，如果小於零，則賦值 currentSum = 0。
這裡主要是要將 currentSum 賦值為零，因為我們正在查詢最大和，如果和變為小於零，則繼續保留它沒有意義。我們只需將 currentSum 重置為零，然後從一個新的子陣列開始。
使用 Kadane 演算法查詢最大子陣列和的 Java 程式碼
import java.util.Scanner;
public class KadaneAlgo {
static int FindMaxSubArraySum(int[] arr, int n) {
int currentSum = 0, maxSum = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
currentSum = Math.max(arr[i], currentSum + arr[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of array: ");
int n = sc.nextInt();
int[] arr = new int[n];
System.out.println("Enter " + n + " Array elements: ");
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
long maxSum = FindMaxSubArraySum(arr, n);
System.out.println("Max Subarray Sum is: " + maxSum);
}
}
輸出
更新於: 2024-09-09
108 次瀏覽
廣告