[LC] 0053 Maximum Subarray

Java

/**
 * <a href="https://leetcode-cn.com/problems/maximum-subarray/">Maximum Subarray</a>
 * 数组；分治；动态规划
 */
class Solution {
    public int maxSubArray(int[] nums) {
        int thisSum = 0, maxSum = Integer.MIN_VALUE;
        for (int num : nums) {
            thisSum += num;
            maxSum = Math.max(maxSum, thisSum);
            if (thisSum < 0) {
                thisSum = 0;
            }
        }
        return maxSum;
    }
}

C++

#include <iostream>

using namespace std;

const int INF = 0x3f3f3f3f;

class Solution {
public:
    int maxSubArray(vector<int> &nums) {
        int n = nums.size();
        int thisSum = 0, maxSum = -INF;
        for (int i = 0; i < n; i++) {
            thisSum += nums[i];
            if (thisSum > maxSum)
                maxSum = thisSum;
            if (thisSum < 0)
                thisSum = 0;
        }
        return maxSum;
    }
};