题目链接
解题思路:
dp(动态规划)思想,使用备份数组将每一步的最优解保存在相应位置,下一步直接调用上一步结果即可
状态转移方程:(temp是备份数组,arr是原数组)——通俗的来说就是,每一项面临着被不被选的选择,如果选择,那么至少结果得比当前值要更大,否则当前最优解就是当前项本身
temp[i] = temp[i-1] + arr[i]>arr[i]?temp[i-1] + arr[i]:arr[i];
下面是源代码
1.ac代码,仅仅返回最大值
public int FindGreatestSumOfSubArray(int[] arr){ if(arr.length==0||arr==null)return 0; int[] temp = new int[arr.length]; int max = arr[0]; temp[0] = arr[0]; for(int i = 1;i<arr.length;++i){ temp[i] = temp[i-1] + arr[i]>arr[i]?temp[i-1] + arr[i]:arr[i]; if(temp[i]>max) max = temp[i]; } return max; }
2.返回最优解数组(第一项是状态转移数组,第二项是到此项为止的最优解)
public int[][] FindGreatestSumOfSubArray(int[] arr){ if(arr.length==0||arr==null)return null; int[][] temp = new int[arr.length][2]; int max = arr[0]; temp[0][1] = arr[0]; temp[0][0] = arr[0]; for(int i = 1;i<arr.length;++i){ temp[i][0] = temp[i-1][0] + arr[i]>arr[i]?temp[i-1][0] + arr[i]:arr[i]; if(temp[i][0]>max) max = temp[i][0]; temp[i][1] = max; } return temp; }
代码已ac
希望能给大家带来帮助
以上