這道題雖然有很多種解法，但我一直嘗試著用動態規劃解，剛入門，用起來很不順手，其中出現了很多錯誤，很多的意想不到，希望通過這道題，對動態規劃能夠更進一步的了解。
這道題是典型的也是動態規劃中最簡單的一道題，求最大子串和的問題。
第一步：分解出子問題。
本題的子問題是：dp[i] 代表前i個數中最大子串的和 ；
第二步：通過遞歸或遞推求出子問題的最優解。
本題中的狀態轉移方程為：if ( dp[i-1] < 0 )
dp[i] = a[i] ;
else
dp[i] = dp[i-1] + a[i] ;
#include
#include
using namespace std ;
int main() {
int n ;
cin >> n ;
int t = 1 ;
while(n--) {
int a[110000] , dp[110000] ;
int m ;
cin >> m ;
for(int i = 0 ; i < m ; i++)
cin >> a[i] ;
dp[0] = a[0] ;
for(int j = 1 ; j < m ; j++) {
if(dp[j-1] < 0)
dp[j] = a[j] ;
else
dp[j] = dp[j-1]+a[j] ;
}
int max = dp[0] ;
int y = 0 ;
for(int k = 1 ; k < m ; k++)
if(dp[k] > max) {
max = dp[k] ;
y = k ;
}
int s = 0 ;
int x = y ;
for( int l = y ; l >= 0 ; l-- ) {
s += a[l] ;
if( s == max ) {
x = l ;
}
}
cout<<"Case "<
中間還是跪了好幾次，數組開的太小了，無語……下次記得數組開大一點，多開一點，又不要錢……
