最大子数组（LintCode）

最大子数组

给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。

样例

给出数组[−2,2,−3,4,−1,2,1,−5,3]，符合要求的子数组为[4,−1,2,1]，其最大和为6

注意

子数组最少包含一个数

挑战

要求时间复杂度为O(n)

若当前和小于0，那么加到下一个数上必然会使和减小，此时抛弃这个和重新求和。当遇到一个负数时，记录下当前已知的最大和。

总耗时: 2721 ms

 public class Solution {

     /**

      * @param nums: A list of integers

      * @return: A integer indicate the sum of max subarray

      */

     public int maxSubArray(int[] nums) {

         int sum = nums[0];

         int max = nums[0];

         for(int i = 1 ;i < nums.length ;i++) {

             if(nums[i] < 0) {

                 if(sum > max) max = sum;

             }

             if(sum < 0) {

                 sum = nums[i];

             }else {

                 sum+=nums[i];

             }

         }

         return max>sum?max:sum;

     }

 }

巴特西

最大子数组（LintCode）

最大子数组

给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。

最新文章

热门文章