多维数组和矩阵----子数组最大累加和
2023-03-14 09:45:28 时间
题目:
给定一个数组arr,返回子数组的最大累加和。例如arr = {1,-2,3,5,-2,6,-1};所有的子数组中[3,5,-2,6]可以累加出最大的和12,所以返回12。
代码:
1 import java.util.Arrays; 2 import java.util.Date; 3 4 /** 5 * 求和最大的连续子数组,有可能不唯一,返回一个即可 6 */ 7 public class MaxSubArray { 8 9 // 暴力破解法 O(N²) 10 static void findByForce(int []arr){ 11 int maxSum = arr[0]; 12 for (int j = 0; j < arr.length; j++) { 13 int sum = arr[j]; // 某个元素为子数组的第一个元素 14 int maxOfJ = sum; 15 16 for (int i = j+1; i < arr.length; i++) { 17 sum += arr[i]; // 累加后续元素 18 if (sum>maxOfJ) { 19 maxOfJ = sum; 20 } 21 } 22 if (maxOfJ>maxSum) { 23 maxSum = maxOfJ; 24 } 25 } 26 System.out.println(maxSum); 27 } 28 29 // 递推法 O(N) 30 static int findByDp(int []arr){ 31 if (arr.length==0) { 32 return 0; 33 } 34 int sumJ = arr[0]; // 前J个元素的最大贡献 35 int max = sumJ; 36 // int left = 0,right = 0; // 最大子数组的左右边界下标 37 for (int j = 1; j < arr.length; j++) { 38 if (sumJ >= 0) { // 左子表的最大和为正,继续向后累加 39 sumJ += arr[j]; 40 } else { 41 sumJ = arr[j]; 42 // left = j;// 丢弃前部分和的同时,更新left 43 } 44 45 if (sumJ > max) { 46 max = sumJ; 47 // right = j;// 更新max的同时更新right 48 } 49 } 50 // System.out.println(max+",left="+left+",right:"+right); 51 return max; 52 } 53 /** 54 * 获取指定范围指定个数的随机数组成的数组 55 */ 56 public static int[] getRandomArr(int length, int min, int max) { 57 int[] arr = new int[length]; 58 for (int i = 0; i < length; i++) { 59 arr[i] = (int) (Math.random() * (max + 1 - min) + min); 60 } 61 return arr; 62 } 63 public static void main(String[] args) { 64 // int []arr = new int[]{1,-2,3,5,-2,6,-1}; 65 int[] arr = getRandomArr(10000, -100, 100); 66 System.out.println("数组:" + Arrays.toString(arr)); 67 // long now = new Date().getTime(); 68 // findByForce(arr); 69 // long next1 = new Date().getTime(); 70 // System.out.println("暴力法,时间消耗:" + (next1 - now)); 71 72 long now = System.currentTimeMillis(); 73 findByForce(arr); 74 long next1 = System.currentTimeMillis(); 75 System.out.println("暴力法,时间消耗:" + (next1 - now)); 76 77 System.out.println(findByDp(arr)); 78 long next2 = System.currentTimeMillis(); 79 System.out.println("递推法,时间消耗:" + (next2 - next1)); 80 } 81 82 }
结果:
注意:上面的代码没有考虑数组全为负数的情况,如果数组全为负数的话,返回数组的最大值即可。
相关文章
- 在 Go 里用 CGO?这 7 个问题你要关注!
- 9款优秀的去中心化通讯软件 Matrix 的客户端
- 求职数据分析,项目经验该怎么写
- 在OKR中,我看到了数据驱动业务的未来
- 火山引擎云原生大数据在金融行业的实践
- OpenHarmony富设备移植指南(二)—从postmarketOS获取移植资源
- 《数据成熟度指数》报告:64%的企业领袖认为大多数员工“不懂数据”
- OpenHarmony 小型系统兼容性测试指南
- 肯睿中国(Cloudera):2023年企业数字战略三大趋势预测
- 适用于 Linux 的十大命令行游戏
- GNOME 截图工具的新旧截图方式
- System76 即将推出的 COSMIC 桌面正在酝酿大变化
- 2GB 内存 8GB 存储即可流畅运行,Windows 11 极致精简版系统 Tiny11 发布
- 迎接 ecode:一个即将推出的具有全新图形用户界面框架的现代、轻量级代码编辑器
- loongarch架构介绍(三)—地址翻译
- Go 语言怎么解决编译器错误“err is shadowed during return”?
- 敏捷:可能被开发人员遗忘的部分
- Denodo预测2023年数据管理和分析的未来
- 利用数据推动可持续发展
- 在 Vue3 中实现 React 原生 Hooks(useState、useEffect),深入理解 React Hooks 的