Maximum Subarray(53) - easy

53— Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example1:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
考え方1:
分析テーマ:

配列がすべて負数である場合、最長子列の値は1つの要素、すなわち最大負数である.

配列中に正の整数が存在する場合、最長子列の値は必ず1つの正の整数から始まるサブ列の累積値である.

の1つのサブストリングが終了する条件は、サブストリングの先頭要素から、後方に遍歴する、累積し、累積した結果が0未満であると、ループを終了し、ループ中に最長子ストリング値を記録することである.

は、複数のサブストリングが発生する可能性がある完全な配列を巡回するが、これらのサブストリングを形成する過程で、最も大きなサブストリング値が記録される.

C++コード:

class Solution {
public:
  int maxSubArray(vector<int>& nums) {
    int len = nums.size();
    if(len < 1) return 0;

    int tmp = 0;
    int result = nums[0]-1;
    int i = 0;
    while(i < len){
      if(nums[i] < 0) {
        result = max(result,nums[i]);
        i++;
      }else if(nums[i] >= 0) {
        //    
        do {
          tmp += nums[i];
          result = max(result, tmp);
          i++;
        }while(tmp >= 0 && i < len);
        tmp = 0;
      }
    }
    return result;
  }
};

整理コードは次の形式です.

class Solution {
public:
   int maxSubArray(vector<int> &nums) {
    int result = nums[0],sum = 0;
    if(nums.size() < 1) return 0;
    for(int i = 0; i < nums.size() ;i++) {
      sum += nums[i];
      result = max(result, sum);
      sum = max(sum,0); //sum   0 ,   sum
    }
    return result;
  }
};

Complexity Analysis:
Time complexity : O( n n n). Space complexity : O( 1 1 1).
考え方2:

動的計画:

最長子列値のサブ列がnums[i]で終わる場合、nums[i]で終わる最長子列値はmax(nums[i]、max[i-1]+nums[i])である.遍歴中に長男の列値を記録する.

  //    
  int maxSubArray(vector<int>& nums) {
    int len = nums.size();
    if(len < 1) return 0;
    vector<int> table(len,0);
    int result;

    table[0] = nums[0];
    result = table[0];
    for(int i = 1; i < len; i++) {
      table[i] = max(nums[i], table[i-1]+nums[i]);
      result = max(result, table[i]);
    }
    return result
  }

Complexity Analysis:
Time complexity : O( n n n). Space complexity : O( 1 1 1).