概要
エンジニア職での就職・転職では会社によってはコーディングテストというものがあります。
新卒でも中途でも入社したい会社というのは誰でもいい環境を求めるのではないでしょうか。
そこで、コーディングテストで振り落とされないためにもLeetCodeというテスト対策ができるサイトでアルゴリズム力を鍛えたいと思います。
問題
整数配列numsが与えられたとき、最大の和を持つ連続した部分配列を見つけて和を返す。
部分配列は少なくとも1つの数を含む。
制約
1 <= nums.length <= 105-104 <= nums[i] <= 104
解説
まず初めに部分配列の合計値と一番大きい合計値を記録するための変数を一番最初の値で初期化します。
MaxSubArray
// 部分配列の合計値記録用変数
var temp = nums[0];
// 最大の部分配列合計値用変数
var maxSum = nums[0];次に取り出した値を部分配列として合計値を記録していきます。
MaxSubArray
// 2番目から探索する
for (int i = 1; i < nums.Length; i++)
{
// 取り出した値を合計値として加算
temp += nums[i];
}そして、合計値が+の値であれば最大合計値と比較して大きい方を最大として更新します。
もし-の値であれば最大合計値を求めるには邪魔な要素となってしまうので、新しく部分配列の探索を開始するために0で初期化します。
全ての値を探索したら最大合計値を返して終了です。
MaxSubArray
// 2番目から探索する
for (int i = 1; i < nums.Length; i++)
{
// 取り出した値を合計値として加算
temp += nums[i];
// 合計値が-にならなければ最大合計値と比較して最大値を更新する
if (temp >= 0)
{
maxSum = Math.Max(maxSum, temp);
}
// -であれば最大合計値を求めるのに邪魔になるので部分配列の合計値をリセットする
else
{
temp = 0;
}
}
return maxSum;ソースコード
Solution.cs
public class Solution {
public int MaxSubArray(int[] nums)
{
// 部分配列の合計値記録用変数
var temp = nums[0];
// 最大の部分配列合計値用変数
var maxSum = nums[0];
// 2番目から探索する
for (int i = 1; i < nums.Length; i++)
{
// 取り出した値を合計値として加算
temp += nums[i];
// 合計値が-にならなければ最大合計値と比較して最大値を更新する
if (temp >= 0)
{
maxSum = Math.Max(maxSum, temp);
}
// -であれば最大合計値を求めるのに邪魔になるので部分配列の合計値をリセットする
else
{
temp = 0;
}
}
return maxSum;
}
}