https://leetcode.com/problems/range-sum-query-mutable/
I am trying to solve this question using dynamic programming.
I guess the guys in leetcode want to limit us to use segment tree or one of the other solutions.
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
namespace DynamicProgrammingQuestions
{
/// <summary>
///https://leetcode.com/problems/range-sum-query-mutable/
/// ["NumArray", "sumRange","sumRange","sumRange","update","update","update","sumRange","update","sumRange","update"]
///[[[0,9,5,7,3]],[4,4], [2,4], [3,3] ,[4,5], [1,7] ,[0,8] ,[1,2],[1,9],[4,4],[3,4]]
/// [ null, 3, 15, 7, null ,null ,null ,12,null,5,null]
/// </summary>
[TestClass]
public class UnitTest1
{
[TestMethod]
public void TestMethod1()
{
int[] nums = {0, 9, 5, 7, 3};
NumArray numArray = new NumArray(nums);
Assert.AreEqual(3, numArray.SumRange(4, 4));
Assert.AreEqual(15, numArray.SumRange(2, 4));
Assert.AreEqual(7, numArray.SumRange(3, 3));
numArray.Update(4,5);
numArray.Update(1,7);
numArray.Update(0,8);
// 8,7,5,7,5
Assert.AreEqual(12, numArray.SumRange(1, 2));
}
}
public class NumArray
{
int[] _dp;
int[] _nums;
public NumArray(int[] nums)
{
_dp = new int[nums.Length + 1];
//0,1,2,3
// 1,4,9
for (int i = 0; i < nums.Length; i++)
{
_dp[i + 1] = _dp[i] + nums[i];
}
_nums = nums;
}
public void Update(int index, int val)
{
int old = _nums[index];
_nums[index] = val;
for (int i = index; i < _dp.Length - 1; i++)
{
_dp[i + 1] = _dp[i + 1] - old + val;
}
}
public int SumRange(int left, int right)
{
return _dp[right + 1] - _dp[left];
}
}
}
here is my code. i'm trying to understand if I can optimize it? can you please suggest runtime performance optimizations?