C# 一维dp代码
public class Solution {
public int MaxSubArray(int[] nums) {
int n = nums.Length;
int[] dp = new int[n];
int result = int.MinValue;
for (int i = 0; i < n; i++){
if (i == 0) dp[i] = nums[0];
else dp[i] = nums[i] + Math.Max(dp[i - 1], 0);
result = Math.Max(dp[i], result);
}
return result;
}
}
C# 一维dp优化/贪心代码
public class Solution {
public int MaxSubArray(int[] nums) {
int n = nums.Length;
int result = int.MinValue;
// 使用last代替dp数组, 将空间复杂度降到O(1)
for (int i = 0, last = 0; i < n; i++){
last = nums[i] + Math.Max(last, 0);
result = Math.Max(last, result);
}
return result;
}
}
Follow up 求子数组区间下标
public class Solution {
public int MaxSubArray(int[] nums) {
int left = 0, right = 0;
int n = nums.Length;
int sum = 0;
int max = int.MinValue;
int start = 0, end = 0;
for (int i = 0; i < n; i++){
if (sum > 0){
sum += nums[i];
right++;
}
else{
sum = nums[i];
left = i;
right = i;
}
if (sum > max){
max = sum;
start = left;
end = right;
}
}
Console.Write($"{start} {end}");
return max;
}
}