O(N^2)
?
package heng.java.level1;
import java.util.Scanner;
public class TheMostLongSequenceSum4 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int m = input.nextInt();
while(m-->0){
int n = input.nextInt();
int [] arr = new int [n];
for (int i = 0; i < n; i++) {
arr[i] = input.nextInt();
}
int max = maxSubSum(arr);
System.out.println(max);
}
}
public static int maxSubSum(int []arr){
int maxSum = 0;
for (int i = 0; i < arr.length; i++) {
int thisSum = 0;
for (int j = i; j < arr.length; j++) {
thisSum += arr[i];
if(thisSum > maxSum){
maxSum = thisSum;
}
}
}
return maxSum;
}
}
?
?O(1)
?
package heng.java.level1;
import java.util.Scanner;
public class TheMostLongSequenceSum3 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int m = input.nextInt();
while(m-->0){
int n = input.nextInt();
int [] arr = new int [n];
for (int i = 0; i < n; i++) {
arr[i] = input.nextInt();
}
int max = maxSubSum(arr);
System.out.println(max);
}
}
public static int maxSubSum(int []arr){
int maxSum = 0, thisSum = 0;
for(int j=0; j<arr.length; j++){
thisSum += arr[j];
if(thisSum > maxSum){
maxSum = thisSum;
}else if(thisSum < 0){
thisSum = 0;
}
}
return maxSum;
}
}
?
O(N)?
遞歸&&分治法：
package heng.java.level1;
import java.util.Scanner;
public class TheMostLongSequenceSum2 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int m = input.nextInt();
while(m-->0){
int n = input.nextInt();
int [] arr = new int [n];
for (int i = 0; i < n; i++) {
arr[i] = input.nextInt();
}
int max = maxSumRec(arr,0,arr.length-1);
System.out.println(max);
}
}
public static int maxSumRec(int []arr, int left, int right){
if(left == right){
if(arr[left] > 0){
return arr[left];
}else{
return 0;
}
}
int center = (left+right)/2;
int maxLeftSum = maxSumRec(arr,left,center);
int maxRightSum = maxSumRec(arr,center+1,right);
int maxLeftBorderSum=0,leftBorderSum=0;
for(int i=center; i>=left; i--){
leftBorderSum += arr[i];
if(leftBorderSum > maxLeftBorderSum){
maxLeftBorderSum = leftBorderSum;
}
}
int maxRightBorderSum=0,rightBorderSum=0;
for(int i=center+1; i<=right; i++){
rightBorderSum += arr[i];
if(rightBorderSum > maxRightBorderSum){
maxRightBorderSum = rightBorderSum;
}
}
int sum = maxRightBorderSum+maxLeftBorderSum;
if(sum < maxLeftSum) sum = maxLeftSum;
if(sum < maxRightSum) sum = maxRightSum;
return sum;
}
}
?
?
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
