24.%d\n Maximum Subarray（最大子數列）

題目給予的條件

Input: [-2, -1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6
int maxSubArray(int* nums, int numsSize) {
}

這是個DP問題，題目意思是從母陣列中找到到子陣列的連續數字最大和。

暴力法：

int max = nums[0];
for (int i = 0; i < numsSize - 1; i++) {
   for (int j = i; j < numsSize - 1; j++) {
         int sum = 0;
         for (int k = i; k < j; k++) {
            sum += nums[k];
         }
         if (sum > max) {
            max = sum;
         }
         printf("%d %d: %2d (%d)\n:", i, j, sum, max);
   }
   return max;
}

i 從第零個元素開始數，j從第 i個元素開始數，k從 i數到 j，把這些元素加起來，賦值給sum，如果sum大於max，sum就是max，return max。

max可設為INT_MIN，或取一個陣列中的元素。此結果用了三重迴圈，結果是TLE。

少一點暴力法：

int max = nums[0];
for (int i = 0; i < numsSize - 1; i++) {
   int sum = 0;
   for (int j = i; j < numsSize - 1; j++) {
         
         sum += nums[j];
         if (sum > max) {
            max = sum;
         }
         printf("%d %d: %2d (%d)\n:", i, j, sum, max);
   }
   return max;
}

每次sum是前一次sum加上一個新的元素，接著打擂台，找出max，以這種方式會少一層迴圈。

DP解法：