題目描述
輸入一個(gè)整型數(shù)組，數(shù)組中的一個(gè)或連續(xù)多個(gè)整數(shù)組成一個(gè)子數(shù)組猛蔽。求所有子數(shù)組的和的最大值黄刚。
要求時(shí)間復(fù)雜度為O(n)。
解題思路
這是一個(gè)典型的動(dòng)態(tài)規(guī)劃問(wèn)題碧浊。
設(shè)f[n]表示以第n個(gè)數(shù)字為結(jié)尾的子數(shù)組的最大值涂邀。
有如下的狀態(tài)方程：f[n] = max(nums[n], f[n-1] + nums[n])。
無(wú)初始狀態(tài)和邊界狀態(tài)箱锐，需要注意的是以第0個(gè)為結(jié)尾的子數(shù)組是沒(méi)有前一個(gè)數(shù)的比勉。
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] f = new int[n];
int result = Integer.MIN_VALUE;
for (int i = 0; i < n; i++) {
f[i] = nums[i];
if (i > 0) {
f[i] = Math.max(f[i], f[i - 1] + nums[i]);
}
if (f[i] > result) {
result = f[i];
}
}
return result;
}
}
