题目

英文

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

中文

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

思路

  • 动态规划。
  • 把求联系最大子序列转化为求当前节点与上一节点的最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int maxSubArray(int* nums, int numsSize) {
    if(numsSize == 0){
        return 0;
    }
    if(numsSize <=1){
        return *nums;
    }
    int tmp = 0;
    int pre =  *nums ;
    nums++;
    
    int ret = pre;
   for(int i = 1; i< numsSize;i++)
   {
       tmp = (pre + *nums) > *nums ? (pre + *nums) : *nums;
       
           // printf("tmp:%d\n", tmp);
           if(tmp > ret)
           {
               ret = tmp;
           }
        
       
       pre = tmp;
       nums++;
   }
    return ret;
}