C++

Divide-Conquer[71% passed]

1 class Solution { 2 public: 3     /** 4      * @param nums: a list of integers 5      * @return: A integer denote the sum of minimum subarray 6      */ 7     int minSubArray(vector
     
       nums) { 8         // write your code here 9         int n = nums.size();10         if (n == 1) {11             return nums[0];12         }13         int *arr = nums.data();14         return helper(arr, n);15     }16     int helper(int *arr, int n) {17         // terminate18         if ( n == 1 ) {19             return arr[0];20         }21         // divide22         int mid = n>>1;23         int ans = min(helper(arr, mid), helper(arr + mid, n - mid));24         // conquer25         int now = arr[mid - 1], may = now;26         for (int i = mid-2; i >= 0; --i) {27             may = min(may, now += arr[i]);28         }29         now = may;30         for (int i = mid; i <= n; ++i) {31             may = min(may, now += arr[i]);32         }33         // return34         return min(may, ans);35     }36 };
     

C++, dp

1 class Solution { 2 public: 3     /** 4      * @param nums: a list of integers 5      * @return: A integer denote the sum of minimum subarray 6      */ 7     int minSubArray(vector
     
       nums) { 8         // write your code here 9         int n = nums.size();10         if (n == 1) {11             return nums[0];12         }13         vector
      
        dp(n);14         dp[0] = nums[0];15         int ans = nums[0];16         for (int i = 1; i < n ; ++i) {17             dp[i] = min(nums[i], dp[i - 1]+nums[i]);18             ans = min(dp[i], ans);19         }20         return ans;21     }22 };
      
     

C++,dp,O(1) space

1 class Solution { 2 public: 3     /** 4      * @param nums: a list of integers 5      * @return: A integer denote the sum of minimum subarray 6      */ 7     int minSubArray(vector
     
       nums) { 8         // write your code here 9         int n = nums.size();10         if (n == 1) {11             return nums[0];12         }13         int endHere = nums[0];14         int ans = nums[0];15         for (int i = 1; i < n ; ++i) {16             endHere = min(nums[i], endHere+nums[i]);17             ans = min(endHere, ans);18         }19         return ans;20     }21 };