0){intn=input.nextInt();int[]arr=newint[" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

最長子序列和(由淺入深)

系統 1654 0

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元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 99视频精品全部 在线 | 久草在线视频免费资源观看 | 日本爱爱视频 | 国产成人精品免费久久久久 | 久久综合狠狠综合久久97色 | 天天操国产 | 欧美亚洲综合网 | 成人午夜影院在线观看 | 五月色婷婷琪琪综合伊人 | 日本免费小视频 | 5060一级毛片| 久久99精品久久久久久久不卡 | 国产萝控精品福利视频免费 | 亚洲va精品中文字幕动漫 | 国产在线精品一区二区高清不卡 | 国产综合色在线视频区 | 高清中文字幕免费观在线 | 中文字幕精品视频在线 | 久久精品国产亚洲麻豆 | 天天操天天插天天干 | 国产二区在线播放 | 邵氏经典三级50部 | 四虎成年永久免费网站 | 2022国内精品免费福利视频 | 加勒比一本大道在线 | 精品新一区二区三区四区 | 国产精品久久久久久久久ktv | 国产成人精品亚洲2020 | 黄色毛片毛茸茸 | 日本-区二区三区免费精品 日本热久久 | 99久久亚洲精品影院 | 精品欧美一区二区精品久久 | 久久综合中文字幕一区二区 | 色网站在线 | 日本不卡免免费观看 | 国产91在线 | 日本 | 真实的国产乱xxxx在线播放 | 欧美日韩一区二区三在线 | 伊人久久精品一区二区三区 | 老子影院午夜 | 午夜在线视频一区二区三区 |