Find the contiguous subarray within an array (containing at least one number) which has the largest sum. 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. click to show more practice.
非常常见的题，剑指offer里记过这个题的解法，动态规划，相当于再背了一遍答案。。
代码：
class Solution { public: int maxSubArray(int A[], int n) { if(n==0) return 0; int sum = A[0],tempsum = A[0]; //不能用0初始化，以防数组中都为负值 for(int i = 1;i < n;++i){//循环从1开始，因为0在初始化时已经考虑了 tempsum = (tempsum > 0) ? tempsum+A[i] : A[i];//和小于0的时候抛弃之前的一串 sum = tempsum > sum ? tempsum : sum; } return sum; } };