53.最大子数组和

/*
 * @lc app=leetcode.cn id=53 lang=typescript
 *
 * [53] 最大子数组和
 */

// @lc code=start
function maxSubArray(nums: number[]): number {
	let dp = Array.from({ length: nums.length }, () => -Infinity);

	dp[0] = nums[0];
	for (let i = 1; i < nums.length; i++) {
		if (dp[i - 1] >= 0) {
			dp[i] = dp[i - 1] + nums[i];
		} else {
			// 舍弃之前结果
			dp[i] = nums[i];
		}
	}
	return Math.max(...dp);
}

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));

// @lc code=end