顿搜
飞过闲红千叶，夕岸在哪
类目归类
[LeetCode 53] Maximum Subarray [Java] [Runtime : 17MS]
09/26
1. Description
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
2. Runtime Distribution
3. Submission Details
4. Example
given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
5. Explanation
[tabby title="DP"]
Let dp[i] stands for the max sum which the contiguous subarray end at i.
(1)、$$dp[0] = nums[0]$$
(2)、$$for(i : 1 \\rightarrow N)$$
$$
dp[i] = max \\{ dp[i - 1] + nums[i], nums[i] \\};
$$
[tabbyending]
6. Code
public class LeetCode0053 {
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int dp[] = new int[nums.length];
dp[0] = nums[0];
int result = dp[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
result = Math.max(result, dp[i]);
}
return result;
}
public static void main(String[] args) {
LeetCode0053 leetcode = new LeetCode0053();
int[] nums = new int[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
System.out.println(leetcode.maxSubArray(nums));
}
}
