2019獨角獸企業重金招聘Python工程師標準>>>

#題目概述

題目的意思是給你一個數列，找到一個子數列，這個子數列的和是所有子數列中和最大的。 當然把數列的所有數都列出來肯定不現實。 黑黑，不知道正不正確，我是先從第一個數開始依次加到最后一個數，并且把每一次加的和存到對應的一個和數組中。這樣得到了一個不間斷的和的數列，但是這樣顯然還是不行，在加的時候你還得判斷一下，當和小于零的時候，就得把起始位置，向后挪一個了。這樣才能保證，每次求得的子序列的和是所有子序列當中和最小的。

#附上代碼：

import java.math.BigDecimal; import java.util.Scanner; import java.util.Stack;public class Main{public static void main(String []args){Scanner cin=new Scanner(System.in);int t=cin.nextInt();int [] num=new int[100000];int [] sum=new int[100000];for (int i=1; i<=t; i++){ int n=cin.nextInt(); for (int j=0; j<n; j++){num[j]=cin.nextInt();}int su=0;int start=0;int end=0;for (int j=0; j<n; j++){sum[j]=0;}for (int j=0; j<n; j++){su+=num[j];sum[j]+=su;if (su<0) su=0;}for (int j=1; j<n; j++){if (sum[end]<sum[j]) end=j;}start=end;while (start>0&&sum[start-1]>=0){start--;}start++;end++;System.out.println("Case "+i+":");System.out.println(sum[end-1]+" "+start+" "+end);if (i<t) System.out.println();}} }

Migrated to https://sheltonsuen.github.io

轉載于:https://my.oschina.net/brainysoon/blog/752080

總結

以上是生活随笔為你收集整理的Max Sum 杭电 1003的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。