题解 | #子数组的最大累加和问题#
子数组的最大累加和问题
http://www.nowcoder.com/practice/554aa508dd5d4fefbf0f86e5fe953abd
动态规划解题
package main
/**
* max sum of the subarray
* @param arr int整型一维数组 the array
* @return int整型
*/
func maxsumofSubarray(arr []int) int {
// write code here
dp := make([]int, len(arr))
ret := arr[0]
dp[0] = ret
l := len(arr)
for i := 1; i < l; i++ {
if dp[i-1] > 0 {
dp[i] = dp[i-1] + arr[i]
} else {
dp[i] = arr[i]
}
ret = max(ret,dp[i])
}
return ret
}
func max(a, b int) int {
if a > b {
return a
}
return b
}