@@ -0,0 +1,1930 @@
+//  Copyright 2016 The Sawdust Open Source Project%0A//%0A// Licensed under the Apache License, Version 2.0 (the %22License%22);%0A// you may not use this file except in compliance with the License.%0A// You may obtain a copy of the License at%0A//%0A//     http://www.apache.org/licenses/LICENSE-2.0%0A//%0A// Unless required by applicable law or agreed to in writing, software%0A// distributed under the License is distributed on an %22AS IS%22 BASIS,%0A// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.%0A// See the License for the specific language governing permissions and%0A// limitations under the License.%0A//%0A%0Apackage dp;%0A%0A/**%0A * %3Cpre%3E%0A *     53. Maximum Subarray%0A * Difficulty: Medium%0A * Find the contiguous subarray within an array%0A * (containing at least one number) which has the largest sum.%0A *%0A * For example, given the array%0A *          %5B%E2%88%922,1,%E2%88%923,4,%E2%88%921,2,1,%E2%88%925,4%5D,%0A *%0A * the contiguous subarray %5B4,%E2%88%921,2,1%5D%0A * has the largest sum = 6.%0A *%0A * More practice:%0A * If you have figured out the O(n) solution,%0A * try coding another solution using the divide and conquer approach, which is more subtle.%0A *%0A *  Tags%0A *          Array%0A *          Dynamic Programming%0A *          Divide and Conquer%0A *%0A *   Similar Problems%0A *          (E) Best Time to Buy and Sell Stock%0A *          (M) Maximum Product Subarray%0A *%0A *%0A *   ===========================================================================%0A *%0A *   O(n) in time  see %7B@link KadaneAlgorithm Kadane Algorithm  %7D%0A *%0A * @see %3Ca href=%22https://leetcode.com/problems/maximum-subarray/%22%3Eleetcode%3C/a%3E%0A */%0Apublic class Leetcode53MaximumSubarray %7B%0A    public int maxSubArray(int%5B%5D nums) %7B%0A        int n = nums.length;%0A        int max = nums%5B0%5D, maxEndingHere = nums%5B0%5D;%0A        for (int i = 1; i %3C n; i++) %7B%0A            maxEndingHere = ((maxEndingHere %3C 0) ? 0 : maxEndingHere) + nums%5Bi%5D;%0A            max = maxEndingHere %3E max ? maxEndingHere : max;%0A        %7D%0A        return max;%0A    %7D%0A%7D%0A

Add Leetcode 53 Maximum Subarray