文章

27

粉丝

492

获赞

10

访问

269.7k

头像
动态规划求最大序列和(重点返回始末位置的元素)
P1334 浙江大学/中国矿业大学机试题
发布于2020年5月9日 18:59
阅读数 9.5k

import java.util.Scanner;

/**情况比较多,题难在返回最大序列和的起始下标。最大序列和用动态规划思想
 * @author 回到原点
 *
 */
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()) {
			int k=sc.nextInt();
			if(k==0) break;
			int[] a=new int[k];
			int[] dp=new int[k];
			int flag=0;
			for(int i=0;i<k;i++) {
				a[i]=sc.nextInt();
			}
			//第一种情况:全为负数
			for(int i=0;i<k;i++) {
				if(a[i]>=0)
				{	flag=1;
					break;
					}
			}
			if(flag==0) {
				System.out.println("0"+" "+a[0]+" "+a[k-1]);
				continue;
			}
			//第二种情况,只有一个数时
			if(k==1) {
				System.out.println(a[0]+" "+a[0]+" "+a[0]);	
				continue;
			}
			//第三种情况,不全为负数,动态规划求最大子序列的和
			dp[0]=a[0];
			int max=dp[0];
			int p=0; //记录最大子序列的下标
			int q=0;
			for(int i=1;i<k;i++) {
				dp[i]=Math.max(dp[i-1]+a[i], a[i]);
				if(dp[i]>max) {
					max=dp[i];
					q=i; //得到最大序列和的尾端下标
				}
			}
			i...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发