力扣 面試題 16.17. 連續數列

面試題 16.17. 連續數列

給定一個整數數組，找出總和最大的連續數列，并傳回總和。

示例：

輸入： [-2,1,-3,4,-1,2,1,-5,4]
輸出： 6
解釋： 連續子數組 [4,-1,2,1] 的和最大，為 6。
      

思路：動态規劃（這裡還需要一個數組m[ ]來判斷是否前面連續數列的更大）

int maxSubArray(int* nums, int numsSize){
    int m[numsSize];
    m[0]=nums[0];
    for(int i=1;i<numsSize;i++){
        m[i]=m[i-1]+nums[i]>nums[i]?m[i-1]+nums[i]:nums[i];
    }
    int temp=m[0];
    for(int i=0;i<numsSize;i++){
      temp=temp>m[i]?temp:m[i];
    }
    return temp;
}