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; } }
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
