文章
27
粉丝
492
获赞
10
访问
269.7k
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...
登录后发布评论
暂无评论,来抢沙发