题目分析
题目要找出一个数列中，和最大的子数列。
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
乍一看想到的是先遍历数列来寻找所有的子数列并求和，同时比较和的大小。但是这个方法的效率太低了。
编程实现
C实现
int maxSubArray(int* nums, int numsSize) {
int sum = 0; //初始化sum
int max = INT_MIN; //初始话max为int型的最小值
for(int i = 0; i < numsSize; i++)
{
if(sum >= 0)
sum += nums[i]; //如果sum为正则加nums[i]
else
sum = nums[i]; //如果sum为负则用num[i]替代sum
if(sum > max)
max = sum;
}
return max;
}
C++实现
这里用到了容器
size_t较为陌生。它是一种“整型”类型，里面保存的是一个整数，就像int, long那样。这种整数用来记录一个大小(size)。size_t的全称应该是size type，就是说“一种用来记录大小的数据类型”。通常我们用sizeof(XXX)操作，这个操作所得到的结果就是size_t类型。因为size_t类型的数据其实是保存了一个整数，所以它也可以做加减乘除，也可以转化为int并赋值给int类型的变量。 它是一个与机器相关的unsigned类型，其大小足以保证存储内存中对象的大小。
例如：bitset的size操作返回bitset对象中二进制位中1的个数，返回值类型是size_t。
例如：在用下标访问元素时，vector使用vector::size_type作为下标类型，而数组下标的正确类型则是size_t。vector使用的下标实际也是size_t，源码是typedef size_t size_type。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if (nums.size() == 0) return 0;
else if (nums.size() == 1) return nums.at(0);
int int_local_max = nums.at(0), int_global_max = nums.at(0);
size_t sz_length = nums.size();
for (size_t i = 1; i != sz_length; ++i) {
int_local_max = max(int_local_max + nums.at(i), nums.at(i));
int_global_max = max(int_local_max, int_global_max);
}
return int_global_max;
}
};
