[Leetcode] 1749. Maximum Absolute Sum of Any Subarray

8334 ワード
algorithm テキストリンク
https://leetcode.com/problems/maximum-absolute-sum-of-any-subarray/
入力:整数配列
出力:ローカル配列の絶対値の最大値
局所配列の最大値を求める問題であるため、카데인 알고리즘を用いることができる.なお,部分配列の和に対して絶対値をとるため,負の値の最大値が答えとなる場合もある.この場合,入力配列のすべての記号を置き換えた後,カードデインアルゴリズムをもう一度実行すると答えが見つかる.
コード#コード#
class Solution {
    public int maxAbsoluteSum(int[] nums) {

		int[] positiveDp = new int[nums.length];
		positiveDp[0] = nums[0];
		kadane(nums, positiveDp);

		for (int i = 0; i < nums.length; i++) {
			nums[i] *= -1;
		}

		int[] negativeDp = new int[nums.length];
		negativeDp[0] = nums[0];
		kadane(nums, negativeDp);

		int maxSum = 0;
		for (int i = 0; i < positiveDp.length; i++) {
			if (maxSum < positiveDp[i])
				maxSum = positiveDp[i];
		}

		for (int i = 0; i < negativeDp.length; i++) {
			if (maxSum < negativeDp[i])
				maxSum = negativeDp[i];
		}

		return maxSum;
    }
    
	static void kadane(int[] nums, int[] dp) {
		for (int i = 1; i < dp.length; i++) {
			if (nums[i] < dp[i - 1] + nums[i])
				dp[i] = dp[i - 1] + nums[i];
			else
				dp[i] = nums[i];
		}
	}
}
ASP.NETにおけるExecuteNonQuery()メソッドの使い方
[アルゴリズム]Programmers式の最大化